oj.uz

Submission #124479

# Submission time Handle Problem Language Result Execution time Memory
124479 2019-07-03T11:57:39 Z DJ035 None (KOI17_cook) C++14
56 / 100
 1000 ms 61236 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;
int C[3005][6005], E[3005][6005];
deque<pii> D[3005];
int n, m, s, e, t;
int psum[3005][6005];
int fb[3005];
void input(){
    cin >> n >> m >> s >> e >> t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> psum[i][j];
            psum[i][j] += psum[i][j-1];
        }
        for(int j = m + 1; j < m + s; j++) psum[i][j] = psum[i][j-1];
    }
    for(int i=1;i<=n;i++){
        cin >> fb[i];
    }
}
void trim(deque<pii>& d, int second_th){
    while(!d.empty() && d.front().second < second_th) d.pop_front();
}
void pback(deque<pii>& d, pii v){
    while(!d.empty() && d.back() >= v) d.pop_back();
    d.push_back(v);
}
void pass(pii &n1, pii &n2, pii &n3, pii v){
    if(n1 >= v){
        n3 = n2; n2 = n1; n1 = v;
    }else if(n2 >= v){
        n3 = n2; n2 = v;
    }else if(n3 >= v){
        n3 = v;
    }
}
void dp(){
    for(int i=1;i<=n;i++){
        for(int j = 1; j < s; j++){
            C[i][j] = inf;
        }
    }
    for(int j = s; j < m + s; j++){
        pii m[3] = {{INT_MAX,-1}, {INT_MAX,-1}, {INT_MAX,-1}};
        for(int i = 1; i <= n; i++){
            trim(D[i], j-e);
            if(j - s >= s) pback(D[i], {E[i][j-s],j-s});
            C[i][j] = inf;
            if(!D[i].empty()) C[i][j] = min(C[i][j], D[i].front().first + psum[i][j] + t);
            if(j <= e) C[i][j] = min(C[i][j], psum[i][j]);
            pass(m[0],m[1],m[2],{C[i][j],i});
        }
        for(int i = 1; i <= n; i++){
            for(int b = 0; b < 3; b++){
                if(m[b].second != i && m[b].second != fb[i]){
                    E[i][j] = m[b].first - psum[i][j];
                    break;
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i=1;i<=n;i++){
        ans = min(ans, *min_element(C[i] + m, C[i] + m + s));
    }
    cout << ans << endl;
}
main(){
    input();
    dp();
}

Compilation message

cook.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
13.0 / 13.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct
2 Correct 6 ms 2980 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 7 ms 3064 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 57 ms 7928 KB Output is correct
11 Correct 42 ms 7032 KB Output is correct
12 Correct 58 ms 7736 KB Output is correct
13 Correct 41 ms 7032 KB Output is correct
14 Correct 62 ms 8036 KB Output is correct
15 Correct 58 ms 7848 KB Output is correct
16 Correct 58 ms 7668 KB Output is correct
17 Correct 43 ms 6264 KB Output is correct
18 Correct 53 ms 7928 KB Output is correct
19 Correct 63 ms 6364 KB Output is correct
20 Correct 5 ms 2680 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct
2 Correct 6 ms 2980 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 7 ms 3064 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 57 ms 7928 KB Output is correct
11 Correct 42 ms 7032 KB Output is correct
12 Correct 58 ms 7736 KB Output is correct
13 Correct 41 ms 7032 KB Output is correct
14 Correct 62 ms 8036 KB Output is correct
15 Correct 58 ms 7848 KB Output is correct
16 Correct 58 ms 7668 KB Output is correct
17 Correct 43 ms 6264 KB Output is correct
18 Correct 53 ms 7928 KB Output is correct
19 Correct 63 ms 6364 KB Output is correct
20 Correct 545 ms 57240 KB Output is correct
21 Correct 569 ms 54156 KB Output is correct
22 Correct 551 ms 54588 KB Output is correct
23 Correct 567 ms 58396 KB Output is correct
24 Correct 531 ms 61120 KB Output is correct
25 Correct 565 ms 54848 KB Output is correct
26 Correct 547 ms 54624 KB Output is correct
27 Correct 559 ms 58876 KB Output is correct
28 Correct 564 ms 55716 KB Output is correct
29 Correct 561 ms 61236 KB Output is correct
30 Correct 5 ms 2680 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct
2 Correct 6 ms 2980 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 7 ms 3064 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 57 ms 7928 KB Output is correct
11 Correct 42 ms 7032 KB Output is correct
12 Correct 58 ms 7736 KB Output is correct
13 Correct 41 ms 7032 KB Output is correct
14 Correct 62 ms 8036 KB Output is correct
15 Correct 58 ms 7848 KB Output is correct
16 Correct 58 ms 7668 KB Output is correct
17 Correct 43 ms 6264 KB Output is correct
18 Correct 53 ms 7928 KB Output is correct
19 Correct 63 ms 6364 KB Output is correct
20 Correct 487 ms 21700 KB Output is correct
21 Correct 472 ms 22904 KB Output is correct
22 Correct 470 ms 21500 KB Output is correct
23 Correct 474 ms 26104 KB Output is correct
24 Correct 478 ms 21468 KB Output is correct
25 Correct 482 ms 24756 KB Output is correct
26 Correct 477 ms 21440 KB Output is correct
27 Correct 475 ms 21624 KB Output is correct
28 Correct 474 ms 21948 KB Output is correct
29 Correct 465 ms 25032 KB Output is correct
30 Correct 5 ms 2680 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct
2 Correct 6 ms 2980 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 7 ms 3064 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 57 ms 7928 KB Output is correct
11 Correct 42 ms 7032 KB Output is correct
12 Correct 58 ms 7736 KB Output is correct
13 Correct 41 ms 7032 KB Output is correct
14 Correct 62 ms 8036 KB Output is correct
15 Correct 58 ms 7848 KB Output is correct
16 Correct 58 ms 7668 KB Output is correct
17 Correct 43 ms 6264 KB Output is correct
18 Correct 53 ms 7928 KB Output is correct
19 Correct 63 ms 6364 KB Output is correct
20 Correct 545 ms 57240 KB Output is correct
21 Correct 569 ms 54156 KB Output is correct
22 Correct 551 ms 54588 KB Output is correct
23 Correct 567 ms 58396 KB Output is correct
24 Correct 531 ms 61120 KB Output is correct
25 Correct 565 ms 54848 KB Output is correct
26 Correct 547 ms 54624 KB Output is correct
27 Correct 559 ms 58876 KB Output is correct
28 Correct 564 ms 55716 KB Output is correct
29 Correct 561 ms 61236 KB Output is correct
30 Correct 487 ms 21700 KB Output is correct
31 Correct 472 ms 22904 KB Output is correct
32 Correct 470 ms 21500 KB Output is correct
33 Correct 474 ms 26104 KB Output is correct
34 Correct 478 ms 21468 KB Output is correct
35 Correct 482 ms 24756 KB Output is correct
36 Correct 477 ms 21440 KB Output is correct
37 Correct 475 ms 21624 KB Output is correct
38 Correct 474 ms 21948 KB Output is correct
39 Correct 465 ms 25032 KB Output is correct
40 Correct 647 ms 27904 KB Output is correct
41 Execution timed out 1065 ms 26168 KB Time limit exceeded
42 Halted 0 ms 0 KB -