QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209010#4207. Uplifting Excursionfryan0 1ms4372kbC++202.3kb2023-10-10 02:24:512023-10-10 02:24:51

Judging History

你现在查看的是最新测评结果

  • [2023-10-10 02:24:51]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4372kb
  • [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%