QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#209010 | #4207. Uplifting Excursion | fryan | 0 | 1ms | 4372kb | C++20 | 2.3kb | 2023-10-10 02:24:51 | 2023-10-10 02:24:51 |
answer
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define int long long
#define P pair
#define pi P<int,int>
#define ff first
#define ss second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vsi V<si>
#define vb V<bool>
#define pb push_back
const int INF=1e18;
int m,l;
vi pos;
vi neg;
int num;
int cv=0;
int dpi(int x) {
return x-(l-m*m);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>m>>l; pos=vi(m); neg=vi(m);
for (int i=1; i<=m; i++) {cin>>neg[m-i];}
cin>>num;
for (int i=0; i<m; i++) {cin>>pos[i];}
for (int i=1; i<=m; i++) {
cv-=i*neg[i-1]; num+=neg[i-1];
}
for (int i=1; i<=m; i++) {
int amt=(l-cv)/i;
if (amt<=pos[i-1]) {
num+=amt;
pos[i-1]-=amt;
cv+=amt*i;
} else {
num+=pos[i-1];
cv+=pos[i-1]*i;
pos[i-1]=0;
}
}
for (int i=m; i>=1; i--) {
int amt=(l-cv)/i;
if (amt<=neg[i-1]) {
num-=amt;
neg[i-1]=amt;
cv+=amt*i;
} else {
num-=neg[i-1];
cv+=neg[i-1]*i;
}
}
for (int i=0; i<m; i++) {
pos[i]=min(pos[i],2*m);
neg[i]=min(neg[i],2*m);
}
vi arr;
for (int i=0; i<m; i++) {
int amt=pos[i];
int val=i+1;
int pn=0;
while ((1ll<<pn)<=amt) {
arr.pb((1ll<<pn)*val);
amt-=(1ll<<pn); pn++;
}
if (amt>0) {arr.pb(amt*val);}
}
for (int i=0; i<m; i++) {
int amt=neg[i];
int val=-i-1;
int pn=0;
while ((1ll<<pn)<=amt) {
arr.pb((1ll<<pn)*val);
amt-=(1ll<<pn); pn++;
}
if (amt>0) {arr.pb(amt*val);}
}
int n=sz(arr);
v2i dp(n+1,vi(2*m*m+1,-INF));
dp[0][dpi(cv)]=num;
for (int i=0; i<n; i++) { //push
if (arr[i]<0) {
for (int j=0; j<2*m*m+1; j++) {
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
int nxt=j+arr[i];
if (nxt>=0 && nxt<sz(dp[i+1])) {
dp[i+1][nxt]=max(dp[i+1][nxt],dp[i][j]+1);
}
}
} else {
for (int j=2*m*m; j>=0; j--) {
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
int nxt=j+arr[i];
if (nxt>=0 && nxt<sz(dp[i+1])) {
dp[i+1][nxt]=max(dp[i+1][nxt],dp[i][j]+1);
}
}
}
}
int ans=dp[n][dpi(l)];
if (ans<0) {cout<<"impossible"; return 0;}
cout<<ans<<"\n";
for (auto i:arr) {
//cout<<i<<" ";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3480kb
input:
1 5 0 0 6
output:
5
result:
ok single line: '5'
Test #2:
score: -5
Wrong Answer
time: 1ms
memory: 3592kb
input:
50 2303 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 25 50 0
output:
impossible
result:
wrong answer 1st lines differ - expected: '47', found: 'impossible'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 4372kb
input:
30 38887954194235 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 444113827766 26 511237030935 22 696666627923 315938808146 20 952560827478 924020644151 850666790939 23 587888300072 23 797812801251 911390834853 677171102320 4 2 22 950650764450 278888113729 23 15 15 13 9 637120041802 20 1...
output:
impossible
result:
wrong answer 1st lines differ - expected: '5692035643249', found: 'impossible'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #7:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
0%