oj.uz

Submission #976758

# Submission time Handle Problem Language Result Execution time Memory
976758 2024-05-07T05:25:00 Z vjudge1 Knapsack (NOI18_knapsack) C++17
0 / 100
 38 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pll pair<ll,ll>

const ll MOD=1e9+7;

#define ll int
//KALAU TAKUT RTE

bool cmp (pair<ll,ll> x, pair<ll,ll>y){
	return x.second < y.second;
}

ll expo(ll x, ll y){
	if (y==0) return 1;
	ll ans = expo((x*x)%MOD, y/2);
	if (x%2) return (ans * x)%MOD;
	return ans%MOD;
}

vector<pll> vec[2007];
ll dp[2007][100007];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	ll s,n; cin>>s>>n;
	
	for (int i=1; i<=n;i++){
		ll a,b,c; cin>>a>>b>>c;
		vec[b].pb({a,c});
	}
	for (int i=1; i<=s; i++) sort(vec[i].begin(),vec[i].end(), greater<pll>());
	
	memset(dp, 0 ,sizeof(dp));
	for (int i=1 ;i<=s; i++){
		for (int j=1; j<=s; j++){
			dp[i][j]=dp[i-1][j];
			if (vec[i].size()==0) continue;
			ll cnt =0; ll cur=0;
			for (auto x : vec[i]){
				if (cnt > j) break;
				ll tmp = x.second;
				
				for (int k=0; k<x.second; k++){
					cnt += i;
					cur += x.first;
					if (cnt>j) break;
					dp[i][j] = max(dp[i][j], dp[i-1][j-cnt]+cur);
				}
			}
		}
	}
	cout<<dp[s][s]<<endl;
	
}

Compilation message

knapsack.cpp:10: warning: "ll" redefined
   10 | #define ll int
      | 
knapsack.cpp:4: note: this is the location of the previous definition
    4 | #define ll long long
      | 
knapsack.cpp: In function 'int main()':
knapsack.cpp:45:8: warning: unused variable 'tmp' [-Wunused-variable]
   45 |     ll tmp = x.second;
      |        ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -