結果

問題 No.1324 Approximate the Matrix
コンテスト
ユーザー soto800
提出日時 2020-12-21 23:24:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,599 bytes
コンパイル時間 1,967 ms
コンパイル使用メモリ 173,664 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-21 13:18:35
合計ジャッジ時間 23,403 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 2 TLE * 4 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define lli long long int
#define REP(i,s,n) for(lli i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define MOD (1000000007)
#define TO_STRING(VariableName) # VariableName
#define LOG(xx) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<endl;
#define LOG2(xx,yy) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<endl;
#define LOG3(xx,yy,z) if(DEBUG)cout<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,xx,yy,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(xx)<<"="<<xx<<" "<<TO_STRING(yy)<<"="<<yy<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

lli p[210][210];
lli q[210][210];

lli pow2(lli val){
	return val*val;
}

void solve(){

	lli N,K;
	cin>>N>>K;
	vector<lli> a(N),b(N);
	for(auto &e:a)cin>>e;
	for(auto &e:b)cin>>e;

	lli maxA = -1,maxAI = -1;
	lli maxB = -1,maxBI = -1;

	REP(i,0,N){
		REP(j,0,N){
			cin>>p[i][j];
		}
	}

	REP(i,0,N){
		if(maxA < a[i]){
			maxA = a[i];
			maxAI = i;
		}		
		if(maxB < b[i]){
			maxB = b[i];
			maxBI = i;
		}
	}

	REP(i,0,N){
		REP(j,0,N){
			if(i == maxAI && j == maxBI)continue;
			lli now = min(a[i],b[j]);
			q[i][j] = now;
			a[i]-=now;
			b[j]-=now;
		}
	}

	lli subA = 0,subB = 0;
	REP(i,0,N){
		subA += a[i];
		subB += b[i];
	}
	//LOG2(subA,subB);

	q[maxAI][maxBI] = subA;
/*
	//if(DEBUG){
		REP(i,0,N){
			REP(j,0,N){
				cout<<q[i][j]<<" ";
			}
			cout<<endl;
		}
	//}*/

	lli nowScore = 0;
	REP(i,0,N){
		REP(j,0,N){
			LOG4(i,j,p[i][j],q[i][j]);
			nowScore += pow2(p[i][j]-q[i][j]);
		}
	}
	LOG(nowScore);

	std::random_device rnd;     // 非決定的な乱数生成器を生成
    std::mt19937 mt(rnd());     //  メルセンヌ・ツイスタの32ビット版、引数は初期シード値
    std::uniform_int_distribution<> rand(0, N-1);        // [0, 99] 範囲の一様乱数
	lli cnt = 0;

	lli id[2]={0,0};
	lli jd[2]={0,0};

	std::chrono::system_clock::time_point start;

	start = std::chrono::system_clock::now();
	double elapsed;
	lli ansScore = INF;
	bool check = false;
	while(1){
		if(check || cnt%1000==0){
			std::chrono::system_clock::time_point now = std::chrono::system_clock::now();
    	    elapsed = std::chrono::duration_cast<std::chrono::microseconds>(now-start).count();
    		if(elapsed > 1700*1000){
    			check = true;
    		}
    		if(elapsed > 1950*1000){
    			break;
    		}
    	}

		lli fromI = rand(mt);
		lli toI   = rand(mt);
		lli fromJ = rand(mt);
		lli toJ   = rand(mt);

		if(q[fromI][fromJ] <= 0 || q[toI][toJ] <= 0)continue;
		if(fromI == toI || fromJ == toJ) continue;

		id[0]=fromI,id[1]=toI;
		jd[0]=fromJ,jd[1]=toJ;

		//LOG4(fromI,toI,fromJ,toJ);

		lli nexScore = nowScore;
		REP(i,0,2)REP(j,0,2)nexScore -= pow2(p[id[i]][jd[j]]-q[id[i]][jd[j]]);

		//LOG(nexScore);
		q[fromI][fromJ]--;
		q[fromI][toJ]++;
		q[toI][toJ]--;
		q[toI][fromJ]++;
		REP(i,0,2)REP(j,0,2)nexScore += pow2(p[id[i]][jd[j]]-q[id[i]][jd[j]]);

		if(0){
			LOG3(cnt,nowScore,nexScore);
			REP(i,0,N){
				REP(j,0,N){
					cout<<q[i][j]<<" ";
				}
				cout<<endl;
			}
		}
		nowScore = nexScore;
		chmin(ansScore,nowScore);
		cnt++;
	}

	cout<<ansScore<<endl;

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    lli t=1;
    //cin>>t;
    while(t--)solve();

    return 0;
}
0