QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673361#7787. Maximum RatingAlucardWA 1ms3740kbC++141.7kb2024-10-24 21:55:542024-10-24 21:55:55

Judging History

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

  • [2024-10-24 21:55:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3740kb
  • [2024-10-24 21:55:54]
  • 提交

answer

#include <bits/stdc++.h>
#include <iostream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define i128 _int128
#define fi first
#define se second 
#define pb push_back
#define endl '\n'
//#define int long long
 
const ll INF=0x3f3f3f3f;
const ll N=1e2+9;
const int mod=1e4;

inline int read(){
	int ans=0,sign=1;
	char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			sign=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ans = ans*10 + ch-'0';
		ch = getchar();
	}
	return ans*sign;
}

int x,y,p,q;
int dp[N][N][3];
queue<pair<PII,int>> que;

void bfs(int x,int y){
	que.push({{x,y},0});
	dp[x][y][0]=0;
	while(!que.empty()){
		int nx=que.front().fi.fi;
		int ny=que.front().fi.se;
		int nf=que.front().se;
		que.pop();
		for(int i=nx;i>=0;--i){
			for(int j=ny;j>=0;--j){
				if(i+j<=p && (nx-i+q>=ny-j||nx-i==0)){
					if(dp[x-nx+i][y-ny+j][nf^1]>dp[nx][ny][nf]+1){
						dp[x-nx+i][y-ny+j][nf^1]=dp[nx][ny][nf]+1;
						que.push({{x-nx+i,y-ny+j},nf^1});
					}
				}
				
			}
		}
		
	}
	
}

void solve(){
	x=read();y=read();p=read();q=read();
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			for(int k=0;k<=1;++k){
				dp[i][j][k]=1e9;
			}
		}
	}
	bfs(x,y);
	int ans=1e9;
	for(int i=0;i<=y;++i){
		if(dp[x][i][1])ans=min(ans,dp[x][i][1]);
	}
	if(ans>=1e9)cout<<"-1"<<endl;
	else cout<<ans<<endl;
}

 
 
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int _=1;
    // fac[0]=1;
    // for(int i=1;i<=N-9;++i)fac[i]=(fac[i-1]*i)%mod;
    //_=read();
    
    while(_--)solve();
 
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3740kb

input:

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

output:

9

result:

wrong answer 1st numbers differ - expected: '1', found: '9'