QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21564 | #2848. 城市地铁规划 | DaBenZhongXiaSongKuaiDi# | RE | 6ms | 18384kb | C++14 | 1.3kb | 2022-03-07 15:05:47 | 2022-05-08 03:38:29 |
Judging History
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