Submission #425456

#	Time	Username	Problem	Language	Result	Execution time	Memory
425456		errorgorn	Knapsack (NOI18_knapsack)	C++17	73 / 100	1091 ms	1312 KiB

knapsack

#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 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27