akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
constexpr double pi=3.14159265358979;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

void solve(){
    ll a,b;
    cin>>a>>b;
    //任意の偶数nについてn^n+1=1(偶数で始めれば繰り上がりを気にする必要が無い)
    //f(A,B)=f(0,A-1)^f(0,B)よりA,Bの偶奇のみ気をつければ良い
    ll ansA=0,ansB=0;
    if((a-1)%2==0)ansA=a-1;
    if(b%2==0)ansB=b;
    if((a/2)%2==1)ansA^=1;
    if(((b+1)/2)%2==1)ansB^=1;
    cout<<(ansA^ansB)<<"\n";
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
using namespace std;

signed main(){
    map<string,int> map;
    int q;
    cin>>q;
    while(q--){
        int y;
        string k;
        cin>>y>>k;
        if(y==0){
            int x;
            cin>>x;
            map[k]=x;
        }
        else if(y==1){
            auto it=map.find(k);
            cout<<(it!=map.end()?it->second:0)<<endl;
        }
        else if(y==2){
            map.erase(k);
        }
        else{
            string z;
            cin>>z;
            for(auto it=map.lower_bound(k);it!=map.upper_bound(z);it++){
                cout<<it->first<<" "<<it->second<<endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 27820
n = gets.chomp.to_i
    h = gets.chomp.split(/\s/).map{|x| x.to_i}

    if n == 1
        puts 0
        exit
    end

    o = []
    s = 0
    ms = 0
    for i in 0..(n-2)
        o[i] = h[i]-h[i+1]
        if o[i] >= 0
            s += 1
            ms = [s, ms].max
        else
            s = 0
        end
    end

    if o.max < 0
        puts 0
        exit
    end

    puts ms


Measured memory_bytes: 13188
N=int(input().strip())
b=list(map(int,input().split()))

anslist=[]
for _ in range(N):
    for i in reversed(range(len(b))):
        if i+1==b[i]:
            anslist.append(b[i])
            del b[i]
            #print(anslist)
            #print(b)
            break
if len(b)==0:
    for i in reversed(range(len(anslist))):
        print(anslist[i])
else:
    print("-1")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int L[111];

signed main(){
    L[0]=2;L[1]=1;
    for(int i=2;i<111;i++)L[i]=L[i-1]+L[i-2];
    int n;cin>>n;
    cout<<L[n]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
using namespace std;

bool G[10][10]; // グラフを隣接行列で管理する。無方向なので対称にする。


int main() {
    int N, M; cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b; //全部-1してる
        G[a][b] = G[b][a] = true; //道が繋がっているところはture
    }

    // 順列
    vector<int> su(N);
    for (int i = 0; i < N; ++i) su[i] = i; //ベクトルに0〜n-1を格納

    // 順列を全部試すa
    int ans = 0;
    do {
        if (su[0] != 0) break;

        bool ok = true;
        for (int i = 0; i + 1 < N; ++i) {
            int from = su[i];
            int to = su[i+1];
            if (!G[from][to]) ok = false;
        }
        if (ok) ++ans;
    } while (next_permutation(su.begin(), su.end()));

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    cin >> s >> t;

    if (t.size()>s.size()){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }

    bool can = false;
    for (int i = s.size()-1; i>=0; i--){
        if (s.at(i) == '?' || s.at(i) == t.at(t.size()-1)){
            int count = 1;
            int forS = i-1;
            if (t.size() > 1){           
                for (int j = t.size()-2; j>=0; j--){
                    if (forS >= 0){
                        if (s.at(forS) == '?' || s.at(forS) == t.at(j)){//もんだい
                            count++;
                        }else{
                            break;
                        }
                    }

                    forS--;
                }
            }
            forS = i;
            if (count == t.size()){
                for (int j = t.size()-1; j>=0; j--){
                    s.at(forS) = t.at(j);
                    forS--;
                }
                can = true;
                break;
            }
        }
    }

    if (can){
        for (int i = 0; i<s.size(); i++){
            if (s.at(i) == '?'){
                s.at(i) = 'a';
            }
        }
        cout << s << endl;
    }else{
        cout << "UNRESTORABLE" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

H,W = LI()

if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()

ANS = [H,W]
if H % 3 == 1:
    A = [H//3*W,(H-H//3)*(W//2),(H-H//3)*((W+1)//2)]
    ANS.append(max(A)-min(A))
if H % 3 == 2:
    A = [(H+1)//3*W,(H-(H+1)//3)*(W//2),(H-(H+1)//3)*((W+1)//2)]
    ANS.append(max(A)-min(A))
if W % 3 == 1:
    A = [W//3*H,(W-W//3)*(H//2),(W-W//3)*((H+1)//2)]
    ANS.append(max(A)-min(A))
if W % 3 == 2:
    A = [(W+1)//3*H,(W-(W+1)//3)*(H//2),(W-(W+1)//3)*((H+1)//2)]
    ANS.append(max(A)-min(A))

print(min(ANS))


Measured memory_bytes: 61548
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int x, a, b;
  cin >> x >> a >> b;

  int ans = (x - a) % b;
  cout << ans << endl;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
std::string data;
int jd=1;
void solve(){
    if(data.size()%2!=0) {
        jd=0;
    }

    rep(i,data.size()/2){
        if(data.at(2*i)!='h'||data.at(2*i+1)!='i') {
            jd=0;
        }
    }

    if(jd==0) {
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }

}

int main(){
    cin>>data;

    solve();
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    map<ll, ll>cnt;
    ll N;
    cin >> N;
    rep(i, N){
        ll x;
        cin >> x;
        cnt[x]++;
    }
    cin >> N;
    rep(i, N){
        ll x;
        cin >> x;
        if(cnt[x] <= 0){
            cout << "NO" << endl;
            return 0;
        }
        cnt[x]--;
    }
    cout << "YES" << endl;

    return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
#define int long long
int n,a[2002];
int dp[2002][2002][2];
int dfs(int l,int r,int turn){
  if(l==r){
    if(turn)return a[l];
    else return 0;
  }
  if(dp[l][r][turn]!=-1)return dp[l][r][turn];
  int res=0;
  if(turn){
    res=max(res,dfs((l-1+n)%n,r,turn^1)+a[l]);
    res=max(res,dfs(l,(r+1)%n,turn^1)+a[r]);
  }
  else{
    if(a[l]>a[r])res=dfs((l-1+n)%n,r,turn^1);
    else res=dfs(l,(r+1)%n,turn^1);
  }
  return dp[l][r][turn]=res;
}

signed main(){
  memset(dp,-1,sizeof(dp));
  cin>>n;
  r(i,n)cin>>a[i];
  int ans=0;
  r(i,n)ans=max(ans,dfs(i,(i+1)%n,1));
  cout<<ans<<endl;
}


Measured memory_bytes: 65812
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

double f(double x1, double y1, double x2, double y2){
    return sqrt((abs(x2-x1)*abs(x2-x1)) + (abs(y2-y1)*abs(y2-y1)));
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    double x, y;
    cin >>n;
    vector<pair<double, double>> arr;
    for(int i = 0; i < n; i++){
        cin >>x >>y;
        arr.push_back({x, y});
    }
    sort(arr.begin(), arr.end());
    double ans = 0;
    vector<double> cache(9);
    cache[0] = 1;
    cache[1] = 1;
    cache[2] = 2;
    for(int i = 2; i <= 8; i++)
        cache[i] = i * cache[i-1];
    do{
        // calculate current distance sum
        double temp = 0;
        for(int i = 1; i < n; i++){
            // find distance b/w i and i - 1
            temp += f(arr[i].first, arr[i].second, arr[i-1].first, arr[i-1].second);
        }
        ans += temp;
    }while(next_permutation(arr.begin(), arr.end()));
    cout <<fixed <<setprecision(10) <<ans / cache[n];
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;

int main(){
    string a, b;
    int n, cnt1 = 0, cnt2 = 0;
    cin >> n;
    for( int i = 0; i < n; i++){
        cin >> a >> b;
        if( a < b ) cnt2 += 3;
        else if( a > b) cnt1 += 3;
        else cnt1++, cnt2++;
    }
    cout << cnt1 << " " << cnt2 << endl;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main(){
    ll n,k;cin>>n>>k;
    ll h[n];rep(i,0,n-1)cin>>h[i];
    if(n<=k){
        cout<<0<<endl;
        return 0;
    }
    sort(h,h+n);
    ll ans=0;
    rep(i,0,n-k-1)ans+=h[i];
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 1792
#!/usr/bin/env python3
import itertools as it
# import numpy as np

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H, W, K = map(int,input().split(" "))
    S = [[int(_) for _ in input().replace("#","1").replace(".","0")] for _ in range(H)]
    # S = np.array(S)

    kw = []
    for i in range(1,W+1):
        kw += list(it.combinations(range(W),i))
    kh = []
    for i in range(1,H+1):
        kh += list(it.combinations(range(H),i))

    def slice(w,h):
        r = 0
        for w_ in w:
            for h_ in h:
                r += S[h_][w_]
        return r

    ans=0
    for iw in kw:
        for ih in kh:
            if slice(iw,ih) == K: ans+=1
                
    print(ans)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 68024
#include "bits/stdc++.h"
using namespace std;

int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y);
}

int main() {
	long long int a, b, c, d;
	cin >> a >> b >> c >> d;

	long long int sub = b - a + 1;
	long long int divc = (b / c - (a - 1) / c);
	long long int divd = (b / d - (a - 1) / d);
	long long int divcd = (b / (c * d / gcd(c, d))) - ((a - 1) / (c * d / gcd(c, d)));

	cout << sub - divc - divd + divcd << endl;
}


Measured memory_bytes: 256
MOD = 998244353
m = 2*10**5 + 500
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in input().split())

    ans = 0
    for k in range(K+1):
        ans += M * pow(M-1, N - (k + 1), MOD) * COMB(N-1, k)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 78296
while true  
  data = gets
  if data == "0 0\n"
    break
  end
  
  n, r = data.split(nil).map(&:to_i)

  array = []
  n.downto(1) do |i|
    array.push(i)
  end

  while r > 0
    data = gets
    p, c = data.split(nil).map(&:to_i)

    temp = array.slice!(p-1..p-1+c-1)
    array = temp + array
    
    r -= 1
  end

  puts array[0]
end


Measured memory_bytes: 9316
from sys import stdin

cards = {}

n = int(input())
for line in stdin:
    m, num = line.rstrip().split(' ')
    cards[(m, int(num))] = True

for s in ['S','H','C','D']:
    for i in range(1, 14):
        if not (s, i) in cards:
            print("{} {}".format(s, i))

Measured memory_bytes: 7580
def knapsack(N,W,weight,value):
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): 
        dp[0][i]=0
    #DP
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]

n,w=map(int,input().split())
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=map(int,input().split())

print(knapsack(n,w,weight,value))

Measured memory_bytes: 300728
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <string>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    string str;
    cin >> str;
    int len = str.length();

    string str_rev;
    str_rev = str;
    reverse(str_rev.begin(),str_rev.end());

//cout << str << "," << str_rev << endl;

    if(str != str_rev){
        cout << "No" << endl;
        return 0;
    }

    string str2,str2_rev;
    str2 = str.substr(0,(len-1)/2);
    str2_rev = str2;
    reverse(str2_rev.begin(),str2_rev.end());

//cout << str2 << " " << str2_rev << endl;

    if(str2 != str2_rev){
        cout << "No" << endl;
        return 0;
    }

    string str3,str3_rev;
    str3 = str.substr((len+1)/2,len);
    str3_rev = str3;
    reverse(str3_rev.begin(),str3_rev.end());

//cout << str3 << " " << str3_rev << endl;

    if(str3 != str3_rev){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from bisect import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pos = N - bisect(A,0)
zero = A.count(0)
neg = N - pos - zero

def is_ok(m):
    if m < 0:
        k = 0
        l = 1
        for i in range(neg):
            a = A[i]
            while a*A[l] > m:
                l += 1
                if l==N: break
            k += N-l
            if k >= K: return True
            if l==N: break
        return False
    else:
        k = diag = 0
        r = neg-1
        for i in range(neg):
            a = A[i]
            while a*A[r] <= m:
                r -= 1
                if r==-1: break
            k += r+1
            if r>=i: diag += 1
            if r==-1: break
        nz = neg+zero
        l = nz
        for i in range(N-1,nz-1,-1):
            a = A[i]
            while a*A[l] <= m:
                l += 1
                if l==N: break
            k += N-l
            if l<=i: diag += 1
            if l==N: break
        tmp = N*(N-1)//2 - (k-diag)//2
        return tmp >= K

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Measured memory_bytes: 80596
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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; }

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};


int main(){
  int H,W;
  cin >> H >> W;
  int ch, cw, dh, dw;
  cin >> ch >> cw >> dh >> dw;
  ch--;cw--;dh--;dw--;

  vector<string> s(H);
  REP(i,H)cin >> s[i];

  deque<P> q;
  q.emplace_back(ch,cw);

  vvi dist(H, vi(W,INF));
  dist[ch][cw]=0;

  while(!q.empty()){
    int x = q.front().Fi;
    int y = q.front().Se;
//    printf("%d : %d -- %d\n",x,y,dist[x][y]);
    q.pop_front();
    int now = dist[x][y];

    if(dist[x][y] != now) continue;
    REP(i,4){
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(nx < 0 || nx >= H || ny < 0 || ny >= W)continue;
      if(s[nx][ny]=='#')continue;
      if(dist[nx][ny]<=now)continue;
      dist[nx][ny]=now;
      q.emplace_front(nx,ny);
    }

    FOR(i,-2,3)FOR(j,-2,3){
      int nx=x+i;
      int ny=y+j;
      if(nx < 0 || nx >= H || ny < 0 || ny >= W)continue;
      if(s[nx][ny]=='#')continue;
      if(dist[nx][ny]<=now+1)continue;
      dist[nx][ny] = now+1;

      q.emplace_back(nx,ny);
    }
  }

  // REP(i,H)REP(j,W){
  //   cout << dist[i][j] << (j==W-1 ? "\n" : " ");
  // }

  int ans = dist[dh][dw];
  if(ans==INF)ans=-1;
  cout << ans << endl;
}



Measured memory_bytes: 9460
#pragma GCC optimize ("O2")
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

#define DEBUG 0
#define dd if (DEBUG)

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

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, A) for (auto & a : A)
#define all(a) (a).begin (), (a).end ()
#define rall(a) (a).rbegin (), (a).rend ()
#define sz(a) (int) (a).size ()
#define szl(a) (int) (a).length ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;
typedef pair <int, int> pii;
#define f first
#define s second
#define mp(a, b) make_pair((a), (b))
typedef vector <int> vi;
#define pb(a) push_back ((a))

const ll MOD = 1e+9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int INFi = 0x3f3f3f3f;
const ll MAXN = 1e+5+7;

int main ()
{
    FASTIO;
    int i, j, n, w;
    cin >> n >> w;
    vector <ll> V (n), W (n);
    vector <ll> dp (MAXN, INF);
    for (i = 0; i < n; i++)
        cin >> W[i] >> V[i];
    dp[V[0]] = W[0];
    for (i = 1; i < n; i++)
    {
        for (j = MAXN - V[i] - 1; j >= 0; j--)
        {
            dp[j + V[i]] = min (dp[j + V[i]], dp[j] + W[i]);
        }
        dp[V[i]] = min (dp[V[i]], W[i]);
    }
    dd for (i = 0; i < 40; i++)
        cout << dp[i] << ' ';
    dd cout << '\n';
    for (i = MAXN - 1; i >= 0; i--)
        if (dp[i] <= w)
            break;
    cout << i << '\n';

    return 0;
}



Measured memory_bytes: 1024
K,N=map(int,input().split())
A=list(map(int,input().split()))
M = 0
i = 0
while i<N-1:
    if M<(A[i+1]-A[i]):
        M=(A[i+1]-A[i])
    i+=1

print(min(K-M,A[N-1]-A[0]))

Measured memory_bytes: 25928
# coding: utf-8
# Your code here!

S = input()
c=0
if S[0]=='A' and 'C' in S[2:-1]:
    for i in range(len(S)):
        if S[i].isupper():
            c+=1
    if c==2:
        print("AC")
    else:
        print("WA")
else:
    print("WA")

Measured memory_bytes: 2940
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<long long,int> P;
static const int INF=1<<24;

int a[110]={0};
int ta,tb;

int main(){
	while(cin>>ta>>tb){
		a[ta]++;
		a[tb]++;
		rep(i,INF){
			cin>>ta>>tb;
			if((ta||tb)==0) break;
			a[ta]++;
			a[tb]++;
		}
		int cou=0;
		rep(i,110){
			if(a[i]%2==1) cou++;
			if(cou>2) break;
		}
		if(cou==2&&a[1]%2==1&&a[2]%2==1)cout<<"OK"<<endl;
		else cout<<"NG"<<endl;
		memset(a,0,sizeof(a));
	}
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define maxn (int)(2e5)
#define i64 long long
#define pii pair<i64,i64>
#define all(x) x.begin(),x.end()
#define LB(x,v) lower_bound(all(x), v) - x.begin()
#define fread() freopen("in.txt", "r", stdin);
using namespace std;

set<int>S;
void init(){
    S.clear();
}
int main() {
    /*BEFORE SUBMIT, CHECK
    sample i/o format
    statements for debugging are removed/comment out
    global values / stl containers are initialized/cleared for each test (if needed)
    all array size are sufficient
    loop variable or output value doesn't cross min/max limit of input
    */
    // #ifndef ONLINE_JUDGE
    //     fread();
    // #endif
    
    int a,b;   
    while(scanf("%d %d",&a, &b)==2){
        //init();
        string aB = "", bA = "";
        for(int i=0;i<a;i++) aB+=(b+'0');
        for(int i=0;i<b;i++) bA+=(a+'0');    

        printf("%s\n", aB < bA? aB.c_str() : bA.c_str());    
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
map<string,int> mp;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        string s;
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const long mod=1e9+7;
long N,dp[111][6][6][6][6];
long find(int now,int back1,int back2,int back3,int back4){
  if(dp[now][back1][back2][back3][back4]!=-1){
    return dp[now][back1][back2][back3][back4];
  }
  if(back1 == 0 && back2 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back1 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 2 && back4 == 1){
    return 0;
  }
  if(back2 == 1 && back3 == 0 && back4 == 2){
    return 0;
  }
  if(now==N){
    return 1;
  }
  long ans=0;
  for(int i=0;i<4;i++){
    ans+=find(now+1,back2,back3,back4,i);
  }
  return dp[now][back1][back2][back3][back4]=ans%mod;
}

int main(){
  cin>>N;
  memset(dp,-1,sizeof(dp));
  cout<<find(0,4,4,4,4)<<endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define _LL long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
    int n;
    cin >> n;
    int *x = new int[n];
    rep(i, n) cin >> x[i];

    int bestp = 1;
    int bestpow = (1 << 30);

    rep(p, 100)
    {
        int tp = 0;
        rep(i, n) tp += (x[i] - p) * (x[i] - p);
        if( tp < bestpow )
        {
            bestpow = tp;
            bestp = p;
        }
    }

    cout << bestpow << endl;
}

Measured memory_bytes: 3540
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

int n;
vector <int> G[101];
queue <int> Q;
int  d[100];
int  dis[101];


int visit(int x){
  int t,i;
  
  Q.push(x);
  dis[x] = 0;
  d[x] = 1;

  while(Q.empty() == false) {
    
    // cout << "start Q" <<endl;

    t = Q.front();
    Q.pop();

    for(i=0; i<G[t].size();i++) {
      if(d[G[t][i]] == 0 ) {
	d[G[t][i]] = 1;
	dis[G[t][i]] = dis[t] + 1;

	Q.push(G[t][i]);
      }

    }
  }
}
    
int main() {
  
  int i,j,k,l,u,a,t;
  
  
  scanf("%d",&n);

  
  
  for(i=0;i<n;i++){
    d[i] = 0;
    dis[i] = -1;
    scanf("%d %d ",&k,&u);
    
    for(j=0;j<u;j++) {
      scanf("%d",&a);
      G[k-1].push_back(a-1);
      // printf("G[%d][%d] = 1\n",i,k-1);
    }
  }
  
  
  visit(0);

  

  for(i=0;i<n;i++) cout << i+1<<" " << dis[i] <<endl;



  return 0;

    
    
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define debug cerr << "-- " << __LINE__ << " --" << endl
#define MOD 998244353
typedef long long int ll;

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
template <typename T> string to_string(const vector<T> &xs) {string s="["; for(int i=0;i<xs.size();i++) s += (i>0 ? " " : "") + to_string(xs[i]); return s + "]";}



ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
ll gcd(ll a, ll b) { ll x, y; return extgcd(a, b, x, y);}

class llm{
	ll n;
public:
	llm(){n = 0;}
	llm(ll n){this->n = (n >= 0) ? (n % MOD) : (MOD - 1 - (-n-1 % MOD));}
	operator ll() const {return n;}
	llm operator+(const llm &y) const{ return llm((ll)*this + (ll)y);}
	llm operator+=(const llm &y) { *this = *this + y; return *this;}
	llm operator-(const llm &y) const{ return llm((ll)*this - (ll)y);}
	llm operator-=(const llm &y) { *this = *this - y; return *this;}
	llm operator-() const{ return llm(0) - *this;}
	llm operator*(const llm &y) const{ return llm((ll)*this * (ll)y);}
	llm operator*=(const llm &y) { *this = *this * y; return *this;}
	llm operator/(const llm &y) const{ return *this * y.inv();}
	llm operator/=(const llm &y) { *this = *this / y; return *this;}
	llm inv() const{
		ll x, y;
		if (extgcd(n, MOD, x, y) == 1) return llm(x);
  		return llm(0); // unsolvable
	}
	friend istream& operator >> (istream& os, llm& x);
	friend ostream& operator << (ostream& os, const llm& x);
};
istream& operator >> (istream& is, llm& x){ll n; is >> n; x = llm(n); return is;}
ostream& operator << (ostream& os, const llm& x){os << (ll)x; return os;}

template<typename T> T comb(ll n, ll k){
	T ret = 1;
	for(ll i=1;i<=k;i++) ret = ret * T(n - k + i) / T(i);
	return ret;
}


int main(void){
	int n; cin >> n;
	vector<int> d(n);
	int mini = INT_MAX, maxi = -1;
	for(int i=0;i<n;i++){
		cin >> d[i];
		mini = min(mini, d[i]);
		maxi = max(maxi, d[i]);
		if (i>0 && d[i]==0) {cout << 0 << endl; return 0;}
	}
	if (d[0] != 0) {cout << 0 << endl; return 0;}

	vector<int> hist(n);
	for(int i=0;i<n;i++) hist[d[i]]++;

	ll ans = 1;
	for(int i=0;i<maxi;i++){
		if (hist[i] == 0) {ans = 0; break;}
		for(int j=0;j<hist[i+1];j++){
			ans = ans * hist[i] % MOD;
		}
	}
	cout << ans << endl;

    return 0;
}













Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
int q;
ll extra, sum1, sum2;
priority_queue <int, vector<int>, less<int>> pq1; 
priority_queue <int, vector<int>, greater<int>> pq2; 
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> q;
 	int sz = 0;
 	while(q--)
 	{
 		int op;
 		cin >> op;
		if(op==1)
		{
			int a, b;
			cin >> a >> b;
			extra += b;
			sz++;
			if(sz(pq1) && a>pq1.top()) 
			{
				pq2.push(a);
				sum2 += a;
			}
			else 
			{
				pq1.push(a);
				sum1 += a;
			}
			while(sz(pq1)>(sz+1)/2)
			{
				pq2.push(pq1.top());
				sum2 += pq1.top();
				sum1 -= pq1.top();
				pq1.pop();
			}
			while(sz(pq1)<(sz+1)/2)
			{
				pq1.push(pq2.top());
				sum1 += pq2.top();
				sum2 -= pq2.top();
				pq2.pop();
			}
		}
		else
		{
			ll x = pq1.top();
			ll res = sum2-sz(pq2)*x + sz(pq1)*x-sum1 + extra;
			cout << x << ' ' << res << '\n';
		}
	}
	return 0;
}


Measured memory_bytes: 3452
#include <iostream>
using namespace std;

int main(){
    int t, h, s;
    while(cin >> t >> h >> s){
        if(t == -1) break;
        int temp = t * 3600 + h * 60 + s;
        temp = 7200 - temp;
        t = temp/3600;
        h = (temp%3600)/60;
        s = temp%60;
        cout << (t/10) << t%10 << ":" << h/10 << h%10 << ":" << s/10 << s%10 << endl;
        temp *= 3;
        t = temp/3600;
        h = (temp%3600)/60;
        s = temp%60;
        cout << (t/10) << t%10 << ":" << h/10 << h%10 << ":" << s/10 << s%10 << endl;
    }
    return 0;
}

Measured memory_bytes: 3076
#include<iostream>
using namespace std;
#define INF 1000000001
int cnt;

void mergeSort(int *,int,int);
void merge(int *,int,int,int);
int main(){
	int N;
	cin>>N;
	int *line=new int[N];
	for(int i=0;i<N;++i){
		cin>>line[i];
	}
	cnt=0;
	mergeSort(line,0,N);
	for(int i=0;i<N;++i){
		cout<<line[i]<<(i<N-1?" ":"\n");
	}
	cout<<cnt<<endl;
	return 0;
}

void mergeSort(int *A,int left,int right){
	if(left + 1 < right){
		int mid = (left + right)/2;
		mergeSort(A,left,mid);
		mergeSort(A,mid,right);
		merge(A,left,mid,right);
	}
}

void merge(int *A,int left,int mid,int right){
	int n1 = mid - left;
	int n2 = right - mid;
	int *L=new int[n1+1],*R=new int[n2+1];
	for(int i=0;i<n1;++i){
		L[i]=A[left + i];
	}
	for(int i=0;i<n2;++i){
		R[i]=A[mid + i];
	}
	L[n1]=INF;
	R[n2]=INF;
	int i=0;
	int j=0;
	for(int k=left;k<right;++k){
		++cnt;
		if(L[i] <= R[j]){
			A[k]=L[i];
			++i;
		}else{
			A[k]=R[j];
			++j;
		}
	}
}


Measured memory_bytes: 65728
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
typedef pair<int,int> P;
#define mod 1000000007



int main(){
    int n;
    cin >> n;
    vector<ll>a(87);
    a[0]=2,a[1]=1;
    for(int i=2;i<87;i++){
        a[i]=a[i-1]+a[i-2];
    }
    cout << a[n] << endl;
    return 0;
}

Measured memory_bytes: 256
def atc_163b(a: str, b: str) -> int:
    NM = a.split(" ")
    N = int(NM[0])
    M = int(NM[1])

    A = b.split(" ")
    A_int = [int(ai) for ai in A]
    play_days = N - sum(A_int)

    if play_days < 0:
        return -1
    else:
        return (play_days)

a = input()
b = input()

print(atc_163b(a, b))


Measured memory_bytes: 9768
def main():
    n, m = map(int, input().split())
    a = [input() for i in range(n)]
    b = [input() for i in range(m)]

    for row in range(n - m + 1):
        current_index = 0
        for index in range(n - m + 1):
            current_index = a[row].find(b[0], index)
            if current_index < 0:
                break

            for i in range(m):
                if a[row + i].find(b[i], current_index) != current_index:
                    break
            else:
                print('Yes')
                return

    print('No')


if __name__ == "__main__":

    main()


Measured memory_bytes: 3064
package main

import "fmt"
import "sort"

func main() {
	var n, k int
	hits := make([]int, n)
	fmt.Scan(&n)
	fmt.Scan(&k)

	if n <= k {
		fmt.Println(0)
	} else {
		var h int
		for i := 0; i < n; i++ {
			fmt.Scan(&h)
			hits = append(hits, h)
		}

		sort.Ints(hits)
		hits = hits[:len(hits)-k]

		var s int64

		for _, v := range hits {
			s = s + int64(v)
		}

		fmt.Println(s)
	}
}

Measured memory_bytes: 8704
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    int n, m;
    int k;
    int ans = 0;

    cin >> n >> m >> k;
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i * (n - j) + j * (m - i) == k) {
                ans = 1;
            }
        }
    }

    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		sc.close();
		int ans = 0;
		StringBuilder sb = new StringBuilder();
		int n = input.length();
		int i = 0;
		while (i < n) {
			char x = 'x';
			if (sb.length() != 0)
				x = sb.charAt(sb.length() - 1);
			char y = input.charAt(i);
			if (sb.length() != 0) {
				if (x != y) {
					ans += 2;
					sb.deleteCharAt(sb.length() - 1);
				} else
					sb.append(y);
			} else {
				sb.append(y);
			}
			// if (sb.length() != 0)
			// x = 'x';
			i++;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 25780
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int xa = min(k,a);
    k -= xa;
    int xb = min(k,b);
    k -= xb;
    int xc = k;
    int ans = xa - xc;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
ll N,M;
string S,T;
ll gcd(ll n,ll m){
	if (m==0){
		return n;
	}
	return gcd(m,n%m);
}
int main(){
	cin>>N>>M>>S>>T;
	map<int,char > mp;
	ll ans=N*M/gcd(N,M);
	REP(i,N){
		mp[ans/N*i]=S[i];
	}
	bool flg=true;
	REP(i,M){
		if (mp.find(ans/M*i)!=mp.end() && mp[ans/M*i]!=T[i]){
			flg=false;
		}
		mp[ans/M*i]=T[i];
	}
	if (flg){
		cout<<ans<<endl;
	}else{
		cout<<-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 8192
import sys
n = int(input())
A=list(map(int,sys.stdin))
cnt = 0
G = [int((3**i-1)/2)for i in range(30,0,-1)]
G = [v for v in G if v <= n]
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
for g in G:
    insertionSort(A, n, g)
print(len(G))
print(*G)
print(cnt)
print(*A,sep='\n')


Measured memory_bytes: 53380
# 最長共通部分列(LCS:Longest Common Subsequence)

q = int(input())

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [0]*(YL+1)
    for i in range(XL):
        dpnew = dp[:]
        for j in range(YL):
            if X[i] == Y[j]:
                dp[j+1] = dpnew[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
    print(dp[YL])


for i in range(q):
    X = list(input())
    Y = list(input())
    LCS(X,Y)



Measured memory_bytes: 5636
#include <iostream>
#include <string>
#include <math.h>
#include <random>
#include <time.h>
	using namespace std;
int main() {
		long long int n, p[100001], yan = 0;
			cin >> n;
		for (int i = 1; i <= n; i++) {
					cin >> p[i];
		
	}
			for (int i = 1; i <= n; i++) {
				if (p[i] == i) {
						yan++;
							if (p[i + 1] == i + 1) {
								i++;
			
			}
			
		}
		
	}
			cout << yan << endl;
	
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



int Q;
int cnt[101010];
bool prime(int x){
	if(x == 1) return 0;
	for(int i = 2; i*i <= x; i++){
		if(x%i == 0) return 0;
	}
	return 1;
}
void solve(){
	for(int i = 1; i < 101010; i++){
		cnt[i] = cnt[i-1];
		if(prime(i) && prime((i+1)/2)) cnt[i]++;
	}
	cin >> Q;
	for(int i = 0; i < Q; i++){
		int a,b;
		cin >> a >> b;
		cout << cnt[b]-cnt[a-1] << endl;
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,odd[ohara],even[ohara];
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
set<ll> st;

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n;
    rep(i,n)cin>>a[i],st.insert(a[i]);
    if(Size(st)==1){
        Cout(n/2);
        return 0;
    }
    rep(i,n){
        if(i%2==0)even[a[i]]++;
        else odd[a[i]]++;
    }

    rep(i,100001){
        if(tmp<even[i]){
            tmp=even[i];
            tmpp=i;
        }
    }
    pos=tmpp;

    tmp=0;
    tmpp=0;
    rep(i,100001){
        if(tmp<odd[i]){
            tmp=odd[i];
            tmpp=i;
        }
    }

    sort(even,even+100000);
    reverse(even,even+100000);
    sort(odd,odd+100000);
    reverse(odd,odd+100000);
    if(pos==tmpp){
        tmp=0;tmpp=0;
        rrep(i,1,100001)cnt+=even[i];
        cnt+=odd[0];
        rrep(i,2,100001)cnt+=odd[i];

        tmp=cnt;
        cnt=0;
        rrep(i,2,100001)cnt+=even[i];
        cnt+=even[0];
        rrep(i,1,100001)cnt+=odd[i];
        tmp=min(tmp,cnt);
        Cout(tmp);
    }
    else{
        rrep(i,1,100001){
            ans+=odd[i];
            ans+=even[i];
        }
        Cout(ans);
    }
    return 0;
}


Measured memory_bytes: 13952
#!/usr/bin/env pypy3

import itertools

NUM_TYPES = 10
INVALID = -1


def in_place_min_costs(min_dist, num_vs=NUM_TYPES):
    for k, i, j in itertools.product(range(num_vs), repeat=3):
        min_dist[i][j] = min(min_dist[i][j], min_dist[i][k] + min_dist[k][j])


def solve(h, w, cs, board):
    in_place_min_costs(cs)
    res = 0
    for i, j in itertools.product(range(h), range(w)):
        b = board[i][j]
        if b != INVALID:
            res += cs[b][1]
    return res


def main():
    h, w = (int(x) for x in input().split())
    cs = [[int(x) for x in input().split()] for _ in range(NUM_TYPES)]
    board = [[int(x) for x in input().split()] for _ in range(h)]
    res = solve(h, w, cs, board)
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40560
#include <bits/stdc++.h>

using namespace std;

struct sushi_t {
  int d;
  int t;
};

static int n, k;
static std::array<sushi_t, 100000> sushis{};
static std::array<int, 100000> worstSushis{0};
static std::array<int, 100000> replaceables{};
static std::array<int, 100000> replacements{};

int64_t solve() {
  int64_t ret0 = 0;
  int64_t nn = 0;
  int replaceableIdx = 0;
  int i = 0;
  for (; i < k; ++i) {
    const auto& s = sushis[i];
    int const prev = worstSushis[s.t];
    worstSushis[s.t] = i + 1;
    ret0 += int64_t(s.d);
    if (!prev) {
      nn++;
    } else {
      replaceables[replaceableIdx++] = s.d;
    }
  }
  int64_t ret = ret0 + nn * nn;
  int replacementIdx = 0;
  for (; i < n; ++i) {
    const auto& s = sushis[i];
    int const prev = worstSushis[s.t];
    worstSushis[s.t] = i + 1;
    if (!prev) {
      replacements[replacementIdx++] = s.d;
    }
  }

  int const replacementSize = replacementIdx;
  replaceableIdx--;
  replacementIdx = 0;
  for (++nn; nn <= k && replaceableIdx >= 0 && replacementIdx < replacementSize;
       ++nn, --replaceableIdx, ++replacementIdx) {
    ret0 -= int64_t(replaceables[replaceableIdx]);
    ret0 += int64_t(replacements[replacementIdx]);
    if (ret0 + int64_t(k) * int64_t(k) <= ret) {
      break;
    }
    ret = std::max(ret0 + nn * nn, ret);
  }
  return ret;
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  std::cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    auto& s = sushis[i];
    std::cin >> s.t >> s.d;
    s.t--;
  }
  std::sort(sushis.begin(), sushis.begin() + n,
            [](const auto& lhs, const auto& rhs) { return lhs.d > rhs.d; });
  std::cout << solve() << std::endl;
  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
using namespace std;
int s[1001];
int main(void){
    // Your code here!
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        int tmp=i;
        for(int j=2;j<=i;j++){
            while(tmp%j==0){
                tmp/=j;
                s[j]++;
            }
        }
    }
    long long  ans=1;
    for(int i=2;i<1001;i++){
        ans*=(s[i]+1);
        ans%=1000000007;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int n, m;
	cin >> n >> m;
	int s = 0 , a[m];
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
		s += a[i];
	}
	if(s > n)
	cout << "-1" << endl;
	else 
	cout << n - s << endl;
	
	return 0;
}

Measured memory_bytes: 3200
S = input()
T = input()

aS = [ord(_) - ord('a') for _ in S]
aT = [ord(_) - ord('a') for _ in T]

aS2 = [[] for _ in range(26)]
aT2 = [[] for _ in range(26)]

for i in range(0, len(aS)):
    aS2[aS[i]].append(i)
    aT2[aT[i]].append(i)

if sorted(aS2) == sorted(aT2):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 17456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> ii;
typedef tuple<int,int,int> i3;
typedef std::pair<int, ii> iii;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<ii> vii;
typedef std::vector<iii> viii;
const int INF=10000000;
#define pb(a) push_back(a)
#define m0(x) memset(x,-1,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define all(x) (x).begin(), (x).end()
const int NMAX=4005;

int grid[NMAX][NMAX];
int memo[NMAX][NMAX];

int count(int x, int y){
  
  if (x<0 or y<0) return 0;
  else if (memo[x][y]!=-1) return memo[x][y];
  else return memo[x][y]=grid[x][y]+count(x-1,y)+count(x,y-1)-count(x-1,y-1);
}



int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  memset(grid,0,sizeof grid);
  memset(memo,-1,sizeof memo);
  int N, K;
  cin >> N >> K;
  int x,y;
  char c;
  while (N--){
    cin >> x >> y >> c;
    if (c=='W') x+=K;
    x=x%(K*2);
    y=y%(K*2);
    grid[x][y]++;
    grid[x+K][y+K]++;
    if (x-K>=0) grid[x-K][y+K]++;
    if (y-K>=0) grid[x+K][y-K]++;
    if (x-K>=0 and y-K>=0) grid[x-K][y-K]++;
    grid[x+K*2][y]++;
    grid[x][y+K*2]++;
    grid[x+K*2][y+K*2]++;
}
  int ans=0;
  for (int x=0; x<=2*K; x++){
    for (int y=0; y<=2*K; y++){
      int nx=x+K-1;
      int ny=y+K-1;
      int temp=count(x+K,y+K)-count(x,y+K)-count(x+K,y)+count(x,y);
      ans=max(ans,temp);
    }
  }
  cout<<ans<<endl;


}


Measured memory_bytes: 125696
package main

import "fmt"

func main() {
	var A, B, C, D int
	fmt.Scan(&A, &B, &C, &D)
	for {
		C -= B
		if C <= 0 {
			break
		}
		A -= D
		if A <= 0 {
			break
		}
	}
	if A > 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1752
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

a,b,c = li()
print(max(0, c - (a-b)))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define CLR(a) memset(a, 0, sizeof(a))
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define FOR(i, a, b)  for(int i=(a); i<(b); i++)
#define REP(i, a, b)  for(int i=(a); i<=(b); i++)
#define DOWN(i, a, b) for(int i=(a); i>=(b); i--)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000009;
const int N= 2e5 +10;

int n;
int a[N], p[N];
ll tmp;
ll cnt, ans;

int main() {
	cin>>n;
	REP(i, 1, n) {
		cin>>a[i];
	}
	DOWN(i, n, 1) {
		if (a[i]==0) p[i]=p[i+1]+1;
		else p[i]=0;
	}

	REP(i, 1, n) {
		tmp=cnt=0;
		int j=i;
		while(j<=n) {
			if (p[j]>0) {
				cnt+=p[j];
				j+=p[j];
			}
			else {
				if ( (tmp|a[j])==(tmp+a[j])) {
					tmp|=a[j];
					cnt++;
					j++;
				}
				else break;
			}
		}
		ans+=cnt;
	}
	cout<<ans<<endl;
	//cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

using namespace std;

typedef long long ll;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;

#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define pi pair<int,int>
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define mod 1000000007
#define pai acos(-1)
#define N 1000

struct tur{
   int w,s,v;
}ar[N+5];
ll dp[N+5][N*10+5];

bool com(tur A,tur B){
   return A.s+A.w<B.s+B.w;
}

int n;

ll call(int idx,int taken){
   if(idx>n||taken>N*10) return 0ll;
   ll &ret=dp[idx][taken];
   if(ret!=-1) return ret;
   ll op1=0,op2=0;
   op1=call(idx+1,taken);
   if(ar[idx].s>=taken) op2=ar[idx].v+call(idx+1,taken+ar[idx].w);
   return ret=max(op1,op2);
}

int main ()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cin>>n;
   for(int i=1;i<=n;i++) cin>>ar[i].w>>ar[i].s>>ar[i].v;
   sort(ar+1,ar+1+n,com);
   memset(dp,-1,sizeof dp);
   cout<<call(1,0)<<"\n";
   return 0;
}



Measured memory_bytes: 82228
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};
fn main() {
    input! {//
        a:i64,b:i64,c:i64,k:i64,
    }
    if k & 1 == 1 {
        println!("{}", b - a);
    } else {
        println!("{}", a - b);
    }
}


Measured memory_bytes: 2140
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  string s;
  cin >> n >> s;
  for(int i=0;i<s.size();i++){
    string str;
    if(s.at(i)+n>'Z') {
      str = s.at(i)+n-'Z'+'A'-1;
      cout << str;
    }
    else {
      str = s.at(i)+n;
      cout << str;
    }
  }
  return 0;
}

Measured memory_bytes: 256