QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524571#8742. 黑白ucup-team052WA 2ms5360kbC++231.2kb2024-08-19 20:12:232024-08-19 20:12:23

Judging History

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

  • [2024-08-19 20:12:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5360kb
  • [2024-08-19 20:12:23]
  • 提交

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'