oj.uz

Submission #124482

# Submission time Handle Problem Language Result Execution time Memory
124482 2019-07-03T12:02:56 Z DJ035 None (KOI17_cook) C++14
56 / 100
 1000 ms 97212 KB 
#include <bits/stdc++.h>



using namespace std;



const int N = 3005;





#define ll long long





ll cost[N][N];



ll dp[N][N];



int ban[N];

ll val[N];



queue<ll> q[N];



set<pair<ll,int> > s[N];





int main(){

    int n,m,S,e,t,i;

    

    

    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>S>>e>>t;

    

    int j;

    for(i=1;i<=n;++i)

        for(j=1;j<=m;++j){

            cin>>cost[i][j];

        }

    for(i=1;i<=n;++i)

        for(j=1;j<=m;++j){

            dp[i][j]= 1e13;

        }

    

    for(i=1;i<=n;++i)

        cin>>ban[i];

    

    set<pair<ll,int> >v;

    set<pair<ll,int> >::iterator it;

    int id;

    

    for(int IND = 1;IND<=m;++IND){    

        v.clear();

        for(id = 1;id<=n;++id){

            v.insert(make_pair(dp[id][IND-1],id));

            

            if(v.size()>3)v.erase(*v.rbegin());

        }

        

        for(id=1;id<=n;++id){

            

            for(it = v.begin();it!= v.end();++it){

                if( (*it).second== id || (*it).second == ban[id])

                    continue;

                q[id].push((*it).first - val[id]);

                break;

            }

            

            if(q[id].size()==S){

                s[id].insert( make_pair(q[id].front(),IND-S));

                q[id].pop();

            }



            while((int)s[id].size()>0){

                int len = (*s[id].begin()).second;

                len = IND- len;

                

                if(len>e){

                    s[id].erase(s[id].begin());

                }

                else

                    break;

            }

            

            val[id]+= cost[id][IND];

            

            if(s[id].size()>0){

                dp[id][IND]= val[id] + (*s[id].begin()).first + t;

                dp[id][IND]= min(dp[id][IND],(ll)1e13);

                

                if(IND==m){

                    dp[id][IND]-=t;

                    

                    while(!q[id].empty()){

                        dp[id][IND] = min(dp[id][IND], q[id].front() +val[id]);

                        q[id].pop();

                    }

                }

            }

        }

    }

    ll ret = 1e13;

    for(i=1;i<=n;++i)

        ret= min(ret, dp[i][m]);

    cout<<ret<<'\n';

}

Compilation message

cook.cpp: In function 'int main()':
cook.cpp:127:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q[id].size()==S){
                ~~~~~~~~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Correct 4 ms 2936 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Correct 4 ms 2936 KB Output is correct
10 Correct 50 ms 9848 KB Output is correct
11 Correct 48 ms 9576 KB Output is correct
12 Correct 57 ms 10232 KB Output is correct
13 Correct 40 ms 9340 KB Output is correct
14 Correct 31 ms 8312 KB Output is correct
15 Correct 44 ms 10104 KB Output is correct
16 Correct 62 ms 11384 KB Output is correct
17 Correct 20 ms 5496 KB Output is correct
18 Correct 35 ms 9208 KB Output is correct
19 Correct 18 ms 5496 KB Output is correct
20 Correct 5 ms 2808 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Correct 4 ms 2936 KB Output is correct
10 Correct 50 ms 9848 KB Output is correct
11 Correct 48 ms 9576 KB Output is correct
12 Correct 57 ms 10232 KB Output is correct
13 Correct 40 ms 9340 KB Output is correct
14 Correct 31 ms 8312 KB Output is correct
15 Correct 44 ms 10104 KB Output is correct
16 Correct 62 ms 11384 KB Output is correct
17 Correct 20 ms 5496 KB Output is correct
18 Correct 35 ms 9208 KB Output is correct
19 Correct 18 ms 5496 KB Output is correct
20 Correct 445 ms 75064 KB Output is correct
21 Correct 759 ms 97212 KB Output is correct
22 Correct 689 ms 94584 KB Output is correct
23 Correct 388 ms 67832 KB Output is correct
24 Correct 265 ms 48376 KB Output is correct
25 Correct 666 ms 91676 KB Output is correct
26 Correct 673 ms 94768 KB Output is correct
27 Correct 380 ms 64284 KB Output is correct
28 Correct 631 ms 86436 KB Output is correct
29 Correct 255 ms 47000 KB Output is correct
30 Correct 5 ms 2808 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Correct 4 ms 2936 KB Output is correct
10 Correct 50 ms 9848 KB Output is correct
11 Correct 48 ms 9576 KB Output is correct
12 Correct 57 ms 10232 KB Output is correct
13 Correct 40 ms 9340 KB Output is correct
14 Correct 31 ms 8312 KB Output is correct
15 Correct 44 ms 10104 KB Output is correct
16 Correct 62 ms 11384 KB Output is correct
17 Correct 20 ms 5496 KB Output is correct
18 Correct 35 ms 9208 KB Output is correct
19 Correct 18 ms 5496 KB Output is correct
20 Correct 853 ms 72032 KB Output is correct
21 Correct 703 ms 56560 KB Output is correct
22 Correct 855 ms 73372 KB Output is correct
23 Correct 208 ms 24056 KB Output is correct
24 Correct 898 ms 68628 KB Output is correct
25 Correct 497 ms 50312 KB Output is correct
26 Correct 884 ms 73176 KB Output is correct
27 Correct 836 ms 73336 KB Output is correct
28 Correct 696 ms 44588 KB Output is correct
29 Correct 515 ms 49960 KB Output is correct
30 Correct 5 ms 2808 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 3064 KB Output is correct
6 Correct 5 ms 3064 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Correct 4 ms 2936 KB Output is correct
10 Correct 50 ms 9848 KB Output is correct
11 Correct 48 ms 9576 KB Output is correct
12 Correct 57 ms 10232 KB Output is correct
13 Correct 40 ms 9340 KB Output is correct
14 Correct 31 ms 8312 KB Output is correct
15 Correct 44 ms 10104 KB Output is correct
16 Correct 62 ms 11384 KB Output is correct
17 Correct 20 ms 5496 KB Output is correct
18 Correct 35 ms 9208 KB Output is correct
19 Correct 18 ms 5496 KB Output is correct
20 Correct 445 ms 75064 KB Output is correct
21 Correct 759 ms 97212 KB Output is correct
22 Correct 689 ms 94584 KB Output is correct
23 Correct 388 ms 67832 KB Output is correct
24 Correct 265 ms 48376 KB Output is correct
25 Correct 666 ms 91676 KB Output is correct
26 Correct 673 ms 94768 KB Output is correct
27 Correct 380 ms 64284 KB Output is correct
28 Correct 631 ms 86436 KB Output is correct
29 Correct 255 ms 47000 KB Output is correct
30 Correct 853 ms 72032 KB Output is correct
31 Correct 703 ms 56560 KB Output is correct
32 Correct 855 ms 73372 KB Output is correct
33 Correct 208 ms 24056 KB Output is correct
34 Correct 898 ms 68628 KB Output is correct
35 Correct 497 ms 50312 KB Output is correct
36 Correct 884 ms 73176 KB Output is correct
37 Correct 836 ms 73336 KB Output is correct
38 Correct 696 ms 44588 KB Output is correct
39 Correct 515 ms 49960 KB Output is correct
40 Execution timed out 1049 ms 95580 KB Time limit exceeded
41 Halted 0 ms 0 KB -