Submission #1336937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336937		Nipphitch	만두 (JOI14_ho_t2)	C++20	25 / 100	1097 ms	47496 KiB

2014_ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int M=505;
const int N=3e6+5;

int n,m,c[M],e[M],p[N],dp1[N],dp2[N],mx;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> p[i];
    sort(p+1,p+1+n,greater <int>());
    for(int i=1;i<=N;i++) dp1[i]=dp1[i-1]+p[i];
    for(int j=1;j<=N;j++) dp2[j]=1e9+7;
    for(int i=1;i<=m;i++){
        cin >> c[i] >> e[i];
        for(int j=N;j>=1;j--){
            if(j-c[i]<0) continue;
            dp2[j]=min(dp2[j],dp2[j-c[i]]+e[i]);
        }
    }
    for(int i=N-1;i>=0;i--) dp2[i]=min(dp2[i],dp2[i+1]);
    mx=0;
    for(int i=1;i<=n;i++) mx=max(mx,dp1[i]-dp2[i]);
    cout << mx;
}

Compilation message (stderr)

2014_ho_t2.cpp: In function 'int main()':
2014_ho_t2.cpp:16:46: warning: iteration 3000004 invokes undefined behavior [-Waggressive-loop-optimizations]
   16 |     for(int i=1;i<=N;i++) dp1[i]=dp1[i-1]+p[i];
      |                                           ~~~^
2014_ho_t2.cpp:16:18: note: within this loop
   16 |     for(int i=1;i<=N;i++) dp1[i]=dp1[i-1]+p[i];
      |                 ~^~~
2014_ho_t2.cpp:17:33: warning: iteration 3000004 invokes undefined behavior [-Waggressive-loop-optimizations]
   17 |     for(int j=1;j<=N;j++) dp2[j]=1e9+7;
      |                           ~~~~~~^~~~~~
2014_ho_t2.cpp:17:18: note: within this loop
   17 |     for(int j=1;j<=N;j++) dp2[j]=1e9+7;
      |                 ~^~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40