Submission #873624


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N,M,C,D,A[2][20];
bool no[20][20];
int dp[1<<20][2][20];
int inf=1e9;
bool B(int x,int y){return (x>>y)&1;}
int bc(int x){
	if(x==0) return 0;
	return __builtin_popcount(x);
}
bool ok[1<<20][20];
int main(){
	cin>>N>>M>>C>>D;
	rep(i,N) cin>>A[0][i]>>A[1][i];
	rep(i,M){
		int x,y;
		cin>>x>>y;
		x--,y--;
		no[x][y]=1;
	}
	rep(i,1<<N) rep(j,N){
		if(B(i,j)){
			ok[i][j]=0;
		}else{
			ok[i][j]=1;
			rep(k,N) if(!B(i,k)&&no[k][j]) ok[i][j]=0;
		}
	}
	rep(i,1<<N) rep(p,2) rep(a,N) dp[i][p][a]=inf;
	dp[0][0][0]=dp[0][1][0]=0;
	rep(i,1<<N){
		rep(p,2){
			int MX=bc(i);
			rep(a,MX+1) if(dp[i][p][a]!=inf){
				rep(x,N) if(ok[i][x]){
					chmin(dp[i|(1<<x)][p][a],dp[i][p][a]+A[p][x]);
					chmin(dp[i|(1<<x)][1-p][a+1],dp[i][p][a]+A[p][x]+C*a+D);
				}
			}
		}
	}
	int ans=inf;
	rep(p,2) rep(a,N) chmin(ans,dp[(1<<N)-1][p][a]);
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task D - 右往左往
User sigma425
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1512 Byte
Status AC
Exec Time 2899 ms
Memory 184704 KB

Judge Result

Set Name All
Score / Max Score 700 / 700
Status
AC × 30
Set Name Test Cases
All 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 10_manual_01, 10_manual_02, 20_v20_001, 20_v20_002, 20_v20_003, 20_v20_004, 20_v20_005, 20_v20_006, 20_v20_007, 20_v20_008, 20_v20_009, 20_v20_010, 20_v20_011, 20_v20_012, 20_v20_013, 20_v20_014, 30_random_01, 30_random_02, 30_random_03, 30_random_04, 30_random_05, 30_random_06, 40_random_01, 40_random_02, 50_maxmove_00, 50_maxmove_01
Case Name Status Exec Time Memory
00_sample_01 AC 4 ms 256 KB
00_sample_02 AC 4 ms 256 KB
00_sample_03 AC 4 ms 256 KB
00_sample_04 AC 4 ms 256 KB
10_manual_01 AC 4 ms 256 KB
10_manual_02 AC 4 ms 256 KB
20_v20_001 AC 2899 ms 184576 KB
20_v20_002 AC 2883 ms 184576 KB
20_v20_003 AC 2796 ms 184576 KB
20_v20_004 AC 2837 ms 184576 KB
20_v20_005 AC 1479 ms 184576 KB
20_v20_006 AC 1475 ms 184576 KB
20_v20_007 AC 1606 ms 184576 KB
20_v20_008 AC 1620 ms 184576 KB
20_v20_009 AC 1496 ms 184576 KB
20_v20_010 AC 1537 ms 184704 KB
20_v20_011 AC 1566 ms 184576 KB
20_v20_012 AC 1588 ms 184576 KB
20_v20_013 AC 1577 ms 184576 KB
20_v20_014 AC 1580 ms 184576 KB
30_random_01 AC 1606 ms 184576 KB
30_random_02 AC 1609 ms 184576 KB
30_random_03 AC 1600 ms 184576 KB
30_random_04 AC 1598 ms 184576 KB
30_random_05 AC 1617 ms 184576 KB
30_random_06 AC 1590 ms 184576 KB
40_random_01 AC 1533 ms 184576 KB
40_random_02 AC 1534 ms 184576 KB
50_maxmove_00 AC 1508 ms 184576 KB
50_maxmove_01 AC 1501 ms 184576 KB