QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524571 | #8742. 黑白 | ucup-team052 | WA | 2ms | 5360kb | C++23 | 1.2kb | 2024-08-19 20:12:23 | 2024-08-19 20:12:23 |
Judging History
answer
#include <bits/stdc++.h>
#define D(...) fprintf(stderr,__VA_ARGS__)
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const int N=200005,B=350;
int n,m,x,y,d[N],a[N],b[N],p[N],q[N],c[N];
LL dp[N],W[N]; // dp:y
vector<pair<int,int> >e[N],E[N]; // e:x E:y
LL query(int i){
if(SZ(e[i])<B){
LL ret=0;
for(auto&u:e[i]){
ret=max(ret,dp[u.first]+u.second);
}
return ret;
}else{
return W[i];
}
}
void upd(int u){ // u:y
for(auto&x:E[u]){
W[x.first]=max(W[x.first],dp[u]+x.second);
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>x>>y;
rep(i,1,x)cin>>d[i];
rep(i,1,n){
cin>>a[i]>>b[i];
}
rep(i,1,m){
cin>>p[i]>>q[i]>>c[i];
e[q[i]].emplace_back(p[i],c[i]);
}
rep(i,1,x){
if(SZ(e[i])>=B){
for(auto&cur:e[i]){
E[cur.first].emplace_back(i,cur.second);
}
}
}
memset(dp,192,sizeof(dp));
dp[0]=0;
rep(i,1,n){
LL old=dp[0];
dp[0]=max(dp[0]+d[b[i]],query(b[i])+d[b[i]]);
dp[a[i]]=max(dp[a[i]],old);
upd(a[i]);
/*rep(j,0,y){
D("%lld ",dp[j]);
}
D("\n");*/
}
printf("%lld\n",dp[0]);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5360kb
input:
100 2 6 WWBBWW WWWWWB 3 8 WWWBBBBB WWWBWWWB BBWWWBWW 5 2 WB BB BB BW BB 6 4 WWBW WBWB WWWW WWWB BBWW BWBW 2 3 WWW WBW 124 125 BWWWWWWWWWWWWWWWWWWWWWWWWWWBWWWWBWWWWWWWWBWWWWWWWWWWWBBBBWWWWWWWWWWWWWWWWWBWWWWWWWWWBWWWWWWWWWWBWWWWWWWWBBWWWWWWWWWWWWWWWWWWB WWWWWWWBWWBWWWWWWWWWWWBWWBWWBWWWWBWWWWWWWWWBWBWB...
output:
0
result:
wrong answer 1st lines differ - expected: 'J', found: '0'