結果
問題 | No.1077 Noelちゃんと星々4 |
ユーザー |
![]() |
提出日時 | 2020-06-12 21:36:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,673 bytes |
コンパイル時間 | 1,738 ms |
コンパイル使用メモリ | 173,960 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-06-24 04:34:17 |
合計ジャッジ時間 | 2,734 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 20 |
ソースコード
·#include<bits/stdc++.h>#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)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; }#define all(x) (x).begin(),(x).end()#pragma GCC optimize("Ofast")using namespace std;typedef long long int ll;typedef long double ld;const ll INF=(1LL<<62);const ld pi=acosl((ld)-1);const ll mod = 1000000007;// const ll mod = 1234567;const int dx[4]={0,1,0,-1};const int dy[4]={1,0,-1,0};const int ddx[8]={1,0,-1,-1,-1,0,1,1};const int ddy[8]={1,1,1,0,-1,-1,-1,0};#define endn "\n"#define TO_STRING(VariableName) # VariableNametemplate <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";returnout;}template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";returnout;}template<class T>void debag(const T &obj){cout<<obj<<endl;}bool solve(){ll n;cin>>n;ll m=2000;vector<ll>y(n);rep(i,n)cin>>y[i];vector<vector<ll>>dp(n+1,vector<ll>(m+1,INF));dp[0][0]=0;vector<ll>ma(m+1,INF);rep(i,n){ll num=INF;rep(j,m+1){chmin(num,dp[i][j]);dp[i+1][j]=num+abs(j-y[i]);}}ll ans=INF;rep(j,m+1)chmin(ans,dp[n][j]);cout<<ans<<endl;return false;}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);solve();}