QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #384101 | #965. Trade | KLPP# | RE | 1ms | 3908kb | C++23 | 1.0kb | 2024-04-09 20:43:44 | 2024-04-09 20:43:45 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const int MX=4000;
lld DP[MX];
lld nx[MX];
const lld INF=1e18;
void solve(){
int n;
lld S;
cin>>n>>S;
vector<pair<lld,lld> >V(n);
rep(i,0,n)cin>>V[i].second;
rep(i,0,n)cin>>V[i].first;
sort(V.begin(),V.end());
reverse(V.begin(),V.end());
rep(i,0,MX)DP[i]=INF;
DP[0]=0;
rep(i,0,n){
rep(j,0,n+1){
nx[j]=DP[j];
}
rep(j,1,n+1)nx[j]=min(nx[j],DP[j-1]+V[i].first*(j-1)+V[i].second);
rep(j,0,n+1){
DP[j]=nx[j];
//cout<<DP[j]<<" ";
}//cout<<endl;
}
rep(i,0,MX){
if(DP[i]>S){
cout<<i-1<<"\n";
return;
}
}
cout<<n<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
input:
2 5 1 1 10 11
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 22 10 1 0 10000
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
1 0 1 0
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
100 100 27 64 97 65 62 73 4 99 39 28 73 80 22 58 49 47 28 63 8 36 1 98 81 74 22 48 44 1 40 46 28 9 42 18 74 97 14 34 53 58 58 34 35 96 32 82 32 17 36 4 46 79 14 15 82 9 7 56 75 73 95 57 2 10 4 59 25 28 91 71 34 26 6 67 52 48 10 36 69 21 84 28 50 7 50 99 64 92 46 83 25 39 57 96 94 87 53 79 20 75 47 9...
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
100 1000000000 92 10 63 82 27 70 84 27 51 82 31 89 36 87 88 4 78 94 98 80 85 36 5 76 72 43 18 57 25 25 68 97 70 15 66 33 21 48 75 96 57 80 87 84 74 83 81 20 2 73 67 10 4 62 77 37 88 48 7 86 56 69 65 20 63 60 95 55 95 1 60 61 82 49 51 69 80 81 63 21 67 56 48 94 42 91 44 19 81 58 16 79 36 66 61 55 73 ...
output:
100
result:
ok 1 number(s): "100"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
100 1000000000 120257228 557511186 386772241 2806964 773458571 348106345 915880772 645203887 358800633 71539475 90761197 668794032 828988857 53801363 163581988 334995719 656620400 748708478 180228942 195311072 632338909 421944369 384634443 401198678 512399678 259642866 663773698 116444419 278003602 ...
output:
14
result:
ok 1 number(s): "14"
Test #7:
score: -100
Runtime Error
input:
10000 10000 553 5780 2647 3284 1514 4103 7505 6005 1418 1765 2996 7475 6899 8544 2259 7743 4145 3695 368 6334 949 4674 3498 9956 1077 7837 4954 5947 4147 7667 1141 3136 7246 5437 7451 7813 8259 7729 5746 5970 1788 7713 4728 3035 6648 619 3256 5830 9341 7117 1475 2492 5235 5734 3590 2280 6501 481 415...