Submission #1354475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354475		hsuan._.0528	Candy (EGOI23_candy)	C++20	100 / 100	119 ms	16564 KiB

Main

//pB
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int, int>
#define S second
#define F first
const int maxn = 100 + 10;
const int inf = 1e18;

int n, f;
LL t;
LL a[maxn];
LL dp[2][maxn][maxn*maxn];
//dp[][i][換到哪個位置][操作次數]=value

signed main(){
    ios_base::sync_with_stdio(0);  cin.tie(0);

    cin>>n>>f>>t;
    int ans=inf;
    for(int i=1; i<=n; i++)   cin>>a[i];
    for(int i=1, c=0; i<=n; i++, c^=1){
        for(int j=1; j<=f; j++){
       //   cout<<j<<" : ";
            for(int k=0; k<n*n; k++){
                if(k >= i-j)  dp[c][j][k]=max({dp[c^1][j][k], dp[c^1][j-1][k], dp[c^1][j-1][k-(i-j)] + a[i]});
                else  dp[c][j][k]=max(dp[c^1][j][k], dp[c^1][j-1][k]);
                if(dp[c][j][k] >= t)  ans=min(ans, k);
                //cout<<dp[c][j][k]<<" ";
            }
        //  cout<<"\n";
        }
      //cout<<"\n";
    }
    
  if(ans==inf)  cout<<"NO";
  else  cout<<ans;
}

Compilation message (stderr)

Main.cpp:9:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int inf = 1e18;
      |                 ^~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 30 / 30
• Subtask 5: 29 / 29