Submission #58713842

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <bitset>
#include <atcoder/all>
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>=b;--i)
#define fore(i, a) for(auto& i : a)
#define PI 3.141592653589793238
using namespace atcoder;
using namespace std;
using mint=modint998244353;
typedef int ll;
typedef pair<ll,ll> pp;
typedef vector<ll> vl;
typedef vector<ulong> vu;
typedef vector<vl> vvl;
typedef vector<pp> vp;
typedef vector<vp> vvp;
typedef priority_queue<pp, vp, greater<pp> > pq;
typedef vector<mint> vm;
typedef vector<vm> vvm;
vm kaijou;
void kaijou_set() {kaijou.push_back(1); rep(i, 1, 2000009)kaijou.push_back(kaijou[i-1] * i); return;}
mint C(ll a, ll b) {if(a < b || b < 0) return 0; return kaijou[a] / (kaijou[b-a] * kaijou[b]);}
template <typename T, typename F>
T bisect(T ok, T bad, F pred) {if(!pred(ok))return ok; while (bad - ok > 1) {T mid = ok + (bad - ok) / 2; (pred(mid) ? ok : bad) = mid;} return bad;}
bool chmin(ll &a, ll b) {if (a > b) {a = b;return true;} return false;}
bool chmax(ll &a, ll b) {if (a < b) {a = b;return true;} return false;}
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
ll gcd(ll x, ll y) {if(y == 0)return x; return gcd(y, x % y); }
ll RU(double a) {ll b = a; return(b == a ? b : b + 1);}
const ll mod=998244353; const ll mof=1000000007;



int main() 
{
    ll n;
    cin>>n;
    ll a[109],b[109];
    ll sum=0;
    rep(i,1,n+1){
        cin>>a[i]>>b[i];
        sum+=b[i];
    }
    if(sum%3>=1){
        cout<<-1<<endl;
        return 0;
    }
    ll ave=sum/3;
    ll dp[109][1509][1509];//i人目まで見て、チーム1の強さがj、チーム2の強さがkであるときの最小移動回数

    rep(i,0,109)rep(j,0,1509)rep(k,0,1509)dp[i][j][k]=1e9;
    dp[0][0][0]=0;

    rep(i,1,n+1){
        rep(j,0,1509){
            rep(k,0,1509){
                //iをチーム1に置く
                if(j-b[i]>=0){
                    ll dpkari=dp[i-1][j-b[i]][k];
                    if(a[i]!=1)++dpkari;
                    chmin(dp[i][j][k],dpkari);
                }

                //iをチーム2に置く
                if(k-b[i]>=0){
                    ll dpkari=dp[i-1][j][k-b[i]];
                    if(a[i]!=2)++dpkari;
                    chmin(dp[i][j][k],dpkari);
                }

                //iをチーム3に置く
                ll dpkari=dp[i-1][j][k];
                if(a[i]!=3)++dpkari;
                chmin(dp[i][j][k],dpkari);
            }
        }
    }

    if(dp[n][ave][ave]==1e9)cout<<-1<<endl;
    else cout<<dp[n][ave][ave]<<endl;
}

Submission Info

Judge Result