QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21564#2848. 城市地铁规划DaBenZhongXiaSongKuaiDi#RE 6ms18384kbC++141.3kb2022-03-07 15:05:472022-05-08 03:38:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:38:29]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:18384kb
  • [2022-03-07 15:05:47]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;
const ll mod=59393; 
int n,k;
ll val[6005],a[6005]; 
ll f[3005][6005],trans[3005][6005]; 
int d[6005],cnt; 
void print(int n,int m) {
	if (n==0) return ;
	int x=trans[n][m];
	d[++cnt]=x;
	print(n-1,m-x);
}
int main() {
	scanf("%d %d",&n,&k);
	for (int i=0;i<=k;i++) {
		scanf("%d",&a[i]); 
	}
	for (int i=1;i<=n-1;i++) {
		ll pw=1; 
		for (int j=0;j<=k;j++) {
			val[i]=(val[i]+a[j]*pw%mod)%mod;
			val[i]=(val[i]+mod)%mod; 
			pw=pw*i%mod; 
		}
	}
	for (int i=0;i<=n;i++) {
		for (int j=0;j<=2*(n-1);j++) {
			f[i][j]=-1e18; 
		}
	}
	f[0][0]=0; 
	for (int x=n-1;x>=1;x--) {
		int t=2*(n-1)/x;
		for (int j=1;j<=t;j++) {
			for (int m=x;m<=2*(n-1);m++) {
				if (f[j][m]<f[j-1][m-x]+val[x]) {
					f[j][m]=f[j-1][m-x]+val[x];
					trans[j][m]=x; 
				}
			}
		}
	}
	cout<<n-1<<' '<<f[n][2*n-2]<<'\n';
	print(n,2*n-2);
	sort(d+1,d+n+1); 
	for (int i=1;i<=n;i++) {
		if (!d[i]) continue ; 
		for (int j=1;j<=n;j++) {
			if (d[j]>=2 || j==n) {
				cout<<i<<' '<<j<<'\n';
				d[i]--,d[j]--; 
				break ; 
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 14168kb

input:

63 7
4 50 14 48 33 13 44 24

output:

62 992106
1 33
2 34
3 34
4 35
5 35
6 36
7 36
8 37
9 37
10 38
11 38
12 39
13 39
14 40
15 40
16 41
17 41
18 42
19 42
20 43
21 43
22 44
23 44
24 45
25 45
26 46
27 46
28 47
29 47
30 48
31 48
32 49
33 49
34 50
35 50
36 51
37 51
38 52
39 52
40 53
41 53
42 54
43 54
44 55
45 55
46 56
47 56
48 57
49 57
50 58...

result:

ok 

Test #2:

score: 0
Accepted
time: 4ms
memory: 18384kb

input:

208 7
23 28 14 16 46 28 26 28

output:

207 3317121
1 106
2 106
3 107
4 107
5 108
6 108
7 109
8 109
9 110
10 110
11 111
12 111
13 112
14 112
15 113
16 113
17 114
18 114
19 115
20 115
21 116
22 116
23 117
24 117
25 118
26 118
27 119
28 119
29 120
30 120
31 121
32 121
33 122
34 122
35 123
36 123
37 124
38 124
39 125
40 125
41 126
42 126
43 ...

result:

ok 

Test #3:

score: -100
Runtime Error

input:

2928 3
27 20 7 29

output:


result: