oj.uz

Submission #425456

# Submission time Handle Problem Language Result Execution time Memory
425456 2021-06-13T04:01:47 Z errorgorn Knapsack (NOI18_knapsack) C++17
73 / 100
 1000 ms 1312 KB 
#include <cstdio>
#include <deque>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> ii;
int s,n,v,w,k,it,e;
int arr[2005];
deque<ii> d;
void print(){
    for (int x=0;x<=s;x++){
        printf("%d ",arr[x]);
    }
    printf("\n");
}
inline int read() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
    return x;
}
int main(){
    //freopen("input.txt","r",stdin);
    memset(arr,-1,sizeof(arr));
    arr[0]=0;
    s=read(),n=read();
    for (int x=0;x<n;x++){
        v=read(),w=read(),k=read();
        for (int y=min(w-1,s-w);y>=0;y--){
            d.clear();
            it=y;
            for (int z=0;it<=s;z++){
                if (arr[it]!=-1){
                    e=arr[it]-v*z;
                    while (!d.empty() && d.back().first<=e) d.pop_back();
                    d.push_back(ii(e,z));
                }
                if (!d.empty()){
                    arr[it]=d.front().first+v*z;
                    if (d.front().second<=z-k)d.pop_front();
                }
                it+=w;
            }
        }
        //print();
    }
    k=0;
    for (int x=0;x<=s;x++){
        k=max(k,arr[x]);
    }
    printf("%d\n",k);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 204 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 2 ms 292 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 ms 292 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Correct 2 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 2 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 0 ms 296 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 2 ms 204 KB Output is correct
33 Correct 2 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 ms 292 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Correct 2 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 2 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 0 ms 296 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 2 ms 204 KB Output is correct
33 Correct 2 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 8 ms 1228 KB Output is correct
36 Execution timed out 1091 ms 1312 KB Time limit exceeded
37 Halted 0 ms 0 KB -