結果
問題 |
No.5021 Addition Pyramid
|
ユーザー |
![]() |
提出日時 | 2025-02-25 21:54:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,785 ms / 2,000 ms |
コード長 | 4,425 bytes |
コンパイル時間 | 4,171 ms |
コンパイル使用メモリ | 307,544 KB |
実行使用メモリ | 6,824 KB |
スコア | 2,418,581 |
最終ジャッジ日時 | 2025-02-25 21:56:19 |
合計ジャッジ時間 | 97,350 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> //#include <atcoder/all> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; //using namespace atcoder; typedef long long ll; typedef unsigned long long ull; #define rep(i,N) for(int i=0;i<(N);++i) #define rrep(i,N) for(int i=(N)-1;i>=0;--i) #define all(A) A.begin(),A.end() using vvi = vector<vector<int>>; using P = pair<int,int>; 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; } template<class T=bool> void YesNo(T flg){ cout << (flg? "Yes\n" : "No\n"); } //時間管理 const double TimeLimit=1780; std::chrono::system_clock::time_point start; std::chrono::system_clock::time_point finish; inline void TimerStart(){ start=finish=chrono::system_clock::now(); } inline void TimerUpdate(){ finish=chrono::system_clock::now(); } double TimeDist(){ return chrono::duration_cast<chrono::milliseconds>(finish-start).count(); } random_device rnd; mt19937 mt(rnd()); default_random_engine eng(rnd()); int NextInt(int minval,int maxval) { uniform_int_distribution<int> distr(minval,maxval); return distr(mt); } vector<vector<vector<ll>>> cross; const ll Mod=1e8; namespace Input{ int N; vector<vector<ll>> A; void Init(){ cin >> N; A.resize(N); rep(i,N){ rep(j,i+1){ ll a;cin >> a; A[i].push_back(a); } } cross.resize(N,vector<vector<ll>>(N,vector<ll>(N,0))); rep(i,N){ cross[i][N-1][i]=1; rrep(j,N){ rep(k,j+1){ cross[i][j][k]%=Mod; if(k<j) cross[i][j-1][k]+=cross[i][j][k]; if(k) cross[i][j-1][k-1]+=cross[i][j][k]; } } } } }; struct Pyramid{ int N; vector<vector<ll>> pyramid; vector<vector<ll>> dist; ll maxDist; void Init(){ N=Input::N; pyramid.resize(N,vector<ll>(N,0)); dist.resize(N,vector<ll>(N,0)); rep(i,N){ pyramid[N-1][i]=Input::A[N-1][i]; } for(int i=N-1;i>0;--i){ rep(j,i+1){ if(j<i) pyramid[i-1][j]+=pyramid[i][j]; if(j) pyramid[i-1][j-1]+=pyramid[i][j]; } } rep(i,N){ rep(j,i+1){ ScoreUpdate(i,j); } } } /// @brief 最下段(N-1,y)の数値をvalue分だけ変更する /// @param y 最下段の何個目か /// @param value 変化量 void Update(const int& y,const ll& value){ maxDist=0; rep(i,N){ rep(j,i+1){ ll add=value*cross[y][i][j]; add%=Mod; pyramid[i][j]+=add; if(cross[y][i][j]){ if(pyramid[i][j]<0){ pyramid[i][j]=Mod-(pyramid[i][j]%Mod); } pyramid[i][j]%=Mod; ScoreUpdate(i,j); } chmax(maxDist,dist[i][j]); } } } void ScoreUpdate(const int& x,const int& y){ dist[x][y]=GetScore(x,y); } ll GetScore(const int& x,const int& y){ ll d=abs(Input::A[x][y]-pyramid[x][y]); return min(d,Mod-d); } }; struct Solver{ int N; Pyramid pyramid; ll bestScore; vector<ll> bestAns; void Init(){ N=Input::N; pyramid.Init(); bestScore=pyramid.maxDist; bestAns=pyramid.pyramid[N-1]; } void Solve(){ TimerStart(); while(TimeDist()<TimeLimit){ int target=NextInt(0,N-1); int value=NextInt(-10,10); pyramid.Update(target,value); if(chmin(bestScore,pyramid.maxDist)){ bestAns=pyramid.pyramid[N-1]; } TimerUpdate(); } } void Output(){ rep(i,N){ if(i) cout << " "; cout << bestAns[i]; } cout << endl; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); Input::Init(); Solver solver; solver.Init(); solver.Solve(); solver.Output(); return 0; }