CSES - Datatähti Open 2021

Submission details
Task:	Programmers
Sender:	rivalq
Submission time:	2021-01-31 12:45:50 +0200
Language:	C++ (C++11)
Status:	READY
Result:	34

Feedback
group	verdict	score
#1	ACCEPTED	34
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.01 s	1, 2, 3	details
#9	ACCEPTED	0.02 s	1, 2, 3	details
#10	ACCEPTED	0.05 s	1, 2, 3	details
#11	ACCEPTED	0.01 s	1, 2, 3	details
#12	ACCEPTED	0.01 s	1, 3	details
#13	ACCEPTED	0.01 s	1, 3	details
#14	ACCEPTED	0.01 s	1, 3	details
#15	ACCEPTED	0.01 s	1, 3	details
#16	ACCEPTED	0.04 s	1, 3	details
#17	ACCEPTED	0.28 s	2, 3	details
#18	ACCEPTED	0.70 s	2, 3	details
#19	ACCEPTED	0.81 s	2, 3	details
#20	TIME LIMIT EXCEEDED	--	2, 3	details
#21	TIME LIMIT EXCEEDED	--	2, 3	details
#22	TIME LIMIT EXCEEDED	--	2, 3	details
#23	TIME LIMIT EXCEEDED	--	2, 3	details
#24	TIME LIMIT EXCEEDED	--	3	details
#25	TIME LIMIT EXCEEDED	--	3	details
#26	TIME LIMIT EXCEEDED	--	3	details
#27	TIME LIMIT EXCEEDED	--	3	details
#28	TIME LIMIT EXCEEDED	--	3	details
#29	TIME LIMIT EXCEEDED	--	3	details
#30	TIME LIMIT EXCEEDED	--	3	details
#31	TIME LIMIT EXCEEDED	--	3	details

Code

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

template<typename flow_t =int, typename cost_t =int>
struct mcSFlow{
    struct Edge{
        cost_t c;
        flow_t f;
        int to, rev;
        Edge(int _to, cost_t _c, flow_t _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
    };
    const cost_t INFCOST = numeric_limits<cost_t>::max()/4;
    const cost_t INFFLOW = numeric_limits<flow_t>::max()/4;
    cost_t epsilon;
    int N, S, T;
    vector<vector<Edge> > G;
    vector<unsigned int> isEnqueued, state;
    mcSFlow(int _N, int _S, int _T):epsilon(0), N(_N), S(_S), T(_T), G(_N){}
    void add_edge(int a, int b, flow_t cap, cost_t cost){
        if(a==b){assert(cost>=0); return;}
        cost*=N;// to preserve integer-values
        epsilon = max(epsilon, abs(cost));
        assert(a>=0&&a<N&&b>=0&&b<N);
        G[a].emplace_back(b, cost, cap, G[b].size());
        G[b].emplace_back(a, -cost, 0, G[a].size()-1);
    }
    flow_t calc_max_flow(){ // Dinic max-flow
        vector<flow_t> dist(N), state(N);
        vector<Edge*> path(N);
        auto cmp = [](Edge*a, Edge*b){return a->f < b->f;};
        flow_t addFlow, retflow=0;;
        do{
            fill(dist.begin(), dist.end(), -1);
            dist[S]=0;
            auto head = state.begin(), tail = state.begin();
            for(*tail++ = S;head!=tail;++head){
                for(Edge const&e:G[*head]){
                    if(e.f && dist[e.to]==-1){
                        dist[e.to] = dist[*head]+1;
                        *tail++=e.to;
                    }
                }
            }
            addFlow = 0;
            fill(state.begin(), state.end(), 0);
            auto top = path.begin();
            Edge dummy(S, 0, INFFLOW, -1);
            *top++ = &dummy;
            while(top != path.begin()){
                int n = (*prev(top))->to;
                if(n==T){
                    auto next_top = min_element(path.begin(), top, cmp);
                    flow_t flow = (*next_top)->f;
                    while(--top!=path.begin()){
                        Edge &e=**top, &f=G[e.to][e.rev];
                        e.f-=flow;
                        f.f+=flow;
                    }
                    addFlow=1;
                    retflow+=flow;
                    top = next_top;
                    continue;
                }
                for(flow_t &i=state[n], i_max = G[n].size(), need = dist[n]+1;;++i){
                    if(i==i_max){
                        dist[n]=-1;
                        --top;
                        break;
                    }
                    if(dist[G[n][i].to] == need && G[n][i].f){
                        *top++ = &G[n][i];
                        break;
                    }
                }
            }
        }while(addFlow);
        return retflow;
    }
    vector<flow_t> excess;
    vector<cost_t> h;
    void push(Edge &e, flow_t amt){
        if(e.f < amt) amt=e.f;
        e.f-=amt;
        excess[e.to]+=amt;
        G[e.to][e.rev].f+=amt;
        excess[G[e.to][e.rev].to]-=amt;
    }
    void relabel(int vertex){
        cost_t newHeight = -INFCOST;
        for(unsigned int i=0;i<G[vertex].size();++i){
            Edge const&e = G[vertex][i];
            if(e.f && newHeight < h[e.to]-e.c){
                newHeight = h[e.to] - e.c;
                state[vertex] = i;
            }
        }
        h[vertex] = newHeight - epsilon;
    }
    const int scale=2;
    pair<flow_t, cost_t> minCostFlow(){
        cost_t retCost = 0;
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost += e.c*(e.f);
            }
        }
        //find feasible flow
        flow_t retFlow = calc_max_flow();
        excess.resize(N);h.resize(N);
        queue<int> q;
        isEnqueued.assign(N, 0); state.assign(N,0);
        // cost scaling
        for(;epsilon;epsilon>>=scale){
            fill(state.begin(), state.end(), 0);
            for(int i=0;i<N;++i)
                for(auto &e:G[i])
                    if(h[i] + e.c - h[e.to] < 0 && e.f) push(e, e.f);
            for(int i=0;i<N;++i){
                if(excess[i]>0){
                    q.push(i);
                    isEnqueued[i]=1;
                }
            }
            while(!q.empty()){
                int cur=q.front();q.pop();
                isEnqueued[cur]=0;
                // discharge
                while(excess[cur]>0){
                    if(state[cur] == G[cur].size()){
                        relabel(cur);
                    }
                    for(unsigned int &i=state[cur], max_i = G[cur].size();i<max_i;++i){
                        Edge &e=G[cur][i];
                        if(h[cur] + e.c - h[e.to] < 0){
                            push(e, excess[cur]);
                            if(excess[e.to]>0 && isEnqueued[e.to]==0){
                                q.push(e.to);
                                isEnqueued[e.to]=1;
                            }
                            if(excess[cur]==0) break;
                        }
                    }
                }
            }
            if(epsilon>1 && epsilon>>scale==0){
                epsilon = 1<<scale;
            }
        }
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost -= e.c*(e.f);
            }
        }
        return make_pair(retFlow, retCost/2/N);
    }
    flow_t getFlow(Edge const &e){
        return G[e.to][e.rev].f;
    }
};
// pass edges in the form ... from to capacity cost
 
// constructor in the form indexOfLastVertex+1,source,sink
 


int solve(){
 		int n,k;cin>>n>>k;
 		int s1=n+1,s=n+2,t=n+3;
 		mcSFlow<int,int> ms(t+1,s1,t);
 		vector<int>a(n+1);
 		ms.add_edge(s1,s,k,0);
 		rep(i,1,n+1){
 			cin>>a[i];
 			if(i%2==0){
 				ms.add_edge(i,t,1,0);
 			}
 			else{
 				ms.add_edge(s,i,1,0);
 			}
 		}
 		sort(a.begin()+1,a.end());
 		for(int i=1;i<=n;i+=2){
 			if(i>0){
 				ms.add_edge(i,i-1,1,a[i]-a[i-1]);
 			}			
 			if(i+1<=n){
 				ms.add_edge(i,i+1,1,a[i+1]-a[i]);
 			}
 		}	
 		cout<<ms.minCostFlow().y<<endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8 3 3 1 2 7 9 3 4 7` view save

correct output
`1` view save

user output
`1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 2 13` view save

correct output
`11` view save

user output
`11` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 10 16 20 6 15 19 12 11 17 20 6 15...` view save

correct output
`6` view save

user output
`6` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`14 5 11 3 8 3 14 8 10 13 11 10 17 1...` view save

correct output
`0` view save

user output
`0` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`15 1 8 5 1 8 18 15 6 20 14 9 10 9 1...` view save

correct output
`0` view save

user output
`0` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10 3 10 19 16 15 12 5 14 8 3 15` view save

correct output
`4` view save

user output
`4` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`202 90 177 187 183 647 616 580 499 78...` view save

correct output
`213` view save

user output
`213` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2000 512 141 583 135 833 900 308 248 58...` view save

correct output
`0` view save

user output
`0` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2000 972 685 4 289 865 93 159 48 866 56...` view save

correct output
`276` view save

user output
`276` view save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2000 1000 698 153 298 118 631 341 238 7 ...` view save

correct output
`517` view save

user output
`517` view save

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2000 1 983 144 449 584 839 166 77 885...` view save

correct output
`0` view save

user output
`0` view save

Test 12

Group: 1, 3

Verdict: ACCEPTED

input
`1464 320 846762124 954854396 12767390 7...` view save

correct output
`35809369` view save

user output
`35809369` view save

Test 13

Group: 1, 3

Verdict: ACCEPTED

input
`2000 231 801945178 924940258 369188694 ...` view save

correct output
`7831421` view save

user output
`7831421` view save

Test 14

Group: 1, 3

Verdict: ACCEPTED

input
`2000 461 464790475 932031556 838378103 ...` view save

correct output
`37272564` view save

user output
`37272564` view save

Test 15

Group: 1, 3

Verdict: ACCEPTED

input
`2000 100 484046702 267135814 995006323 ...` view save

correct output
`1268400` view save

user output
`1268400` view save

Test 16

Group: 1, 3

Verdict: ACCEPTED

input
`2000 996 98352148 438929491 242618159 1...` view save

correct output
`445965905` view save

user output
`445965905` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`65879 19675 896 316 972 476 636 227 716 78...` view save

correct output
`0` view save

user output
`0` view save

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
`200000 53820 995 720 135 767 943 742 191 26...` view save

correct output
`0` view save

user output
`0` view save

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
`200000 32297 527 947 84 851 908 833 339 112...` view save

correct output
`0` view save

user output
`0` view save

Test 20

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99982 561 174 242 275 460 109 664 68...` view save

correct output
`322` view save

user output
(empty)

Test 21

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99955 911 33 314 861 298 117 972 982...` view save

correct output
`245` view save

user output
(empty)

Test 22

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99972 783 1000 673 611 87 452 702 92...` view save

correct output
`290` view save

user output
(empty)

Test 23

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99961 795 136 128 643 60 422 371 839...` view save

correct output
`252` view save

user output
(empty)

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`195426 76599 442872072 619088799 118541378 ...` view save

correct output
`143376538` view save

user output
(empty)

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 1661 894106972 620084612 931442312 ...` view save

correct output
`33089` view save

user output
(empty)

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 86032 211444153 846442677 297198384 ...` view save

correct output
`196001810` view save

user output
(empty)

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 28275 28280312 349705372 96535649 84...` view save

correct output
`11627219` view save

user output
(empty)

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 81473 178022892 112774306 250584651 ...` view save

correct output
`162430841` view save

user output
(empty)

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99987 297598052 494409138 182268523 ...` view save

correct output
`489497036` view save

user output
(empty)

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99971 316462272 843156468 434342923 ...` view save

correct output
`483167476` view save

user output
(empty)

Test 31

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 99964 811543559 465033274 620180191 ...` view save

correct output
`481497328` view save

user output
(empty)

Datatähti Open 2021

Programmers

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Tasks

Submissions (rivalq)