Submission #30814

#	Time	Username	Problem	Language	Result	Execution time	Memory
30814		TAMREF	스트랩 (JOI14_straps)	C++11	50 / 100	946 ms	262144 KiB

straps

#include <bits/stdc++.h>
#define ilb INT_MIN
using namespace std;
unordered_map<int,int> dp[2005], vis[2005];
pair<int,int> f[2005];
int N;
void input(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d %d",&f[i].first,&f[i].second);
    sort(f,f+N,greater<pair<int,int>>());
    dp[0][1]=0;
}
void work_dp(){
    for(int i=0;i<N;i++){
        for(auto x : dp[i]){
            if(!vis[i+1][x.first]){
                dp[i+1][x.first]=ilb;
                vis[i+1][x.first]=1;
            }
            dp[i+1][x.first]=max(dp[i+1][x.first],x.second);
            if(!x.first) continue;
            if(!vis[i+1][x.first+f[i].first-1]){
                dp[i+1][x.first+f[i].first-1]=ilb;
                vis[i+1][x.first+f[i].first-1]=1;
            }
            dp[i+1][x.first+f[i].first-1]=max(dp[i+1][x.first+f[i].first-1],x.second+f[i].second);
        }
    }
}
void output(){
    int t=0;
    for(auto x : dp[N]) t=max(t,x.second);
    printf("%d\n",t);
}
int main(){
    input();
    work_dp();
    output();
}

Compilation message (stderr)

straps.cpp: In function 'void input()':
straps.cpp:8:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
straps.cpp:9:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<N;i++) scanf("%d %d",&f[i].first,&f[i].second);
                                                                 ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 45 / 45
• Subtask 4: 0 / 45