이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define MAXM 2010
long long n;
long long s;
vector<priority_queue<pair<long long,long long>>> niz;
vector<pair<long long,pair<long long,long long>>> pomoc;
long long dp[MAXM];
int main()
{
ios_base::sync_with_stdio(false);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s>>n;
for (long long i=1;i<=n;i++)
{
long long x,y,z;
cin>>x>>y>>z;
niz[y].push({x,z});
}
for (long long i=1;i<=s;i++)
{
long long ans=s/i;
while (ans and niz[i].empty()==false)
{
pair<long long,long long> p=niz[i].top();
niz[i].pop();
long long v=p.first;
long long k=p.second;
for (long long j=1;j<=min(ans,k);j++) pomoc.push_back({v,{i,k}});
ans-=min(ans,k);
}
}
for (long long i=1;i<=s;i++)
{
dp[i]=dp[i-1];
for (long long j=0;j<(long long)pomoc.size();j++)
{
if (i>=pomoc[j].second.first) dp[i]=max(dp[i],dp[i-pomoc[j].second.first]+pomoc[j].first);
}
}
long long sol=0;
for (long long i=1;i<=s;i++) sol=max(sol,dp[i]);
cout<<sol<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |