akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (int) n; i++)
#define reps(i, n) for (int i = 1; i <= (int) n; i++)
#define all(x) (x).begin(), (x).end()
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << x << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
constexpr double pi = 3.1415926535897932384626433832795028;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T1, typename T2> inline bool chmax(T1 &a, const T2 &b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, const T2 &b) { return b < a && (a = b, true); }
struct SetUp { SetUp() { cout << fixed << setprecision(20); }; } setUp;

string A, B;
int N = A.length();
int solve(vint Av, vint Bv) {
    int ret = LLONG_MAX;
    vint Bsum(Bv);
    for (int i = 1; i < N * 3; i++) { Bsum[i] += Bsum[i - 1]; }
    vint l(N), r(N);
    rep(i, N) {
        for (int j = N - 1; j >= 0; j--) {
            if (Bv[i - j + N]) { l[i] = j; }
            if (Bv[i + j + N]) { r[i] = j; }
        }
    }
    rep(i, N) {
        int cur = i;
        priority_queue<pint> plmr;
        rep(j, N) {
            if (Av[j] == Bv[i + j]) { continue; }
            cur++;
            if (Bsum[i + j + N] - Bsum[j + N] > 0) {
                continue;
            }
            plmr.push({l[j], -r[(i + j) % N]});
        }
        int ccur = LLONG_MAX, rmax = 0;
        while (!plmr.empty()) {
            chmin(ccur, plmr.top().first + rmax);
            chmax(rmax, -plmr.top().second);
            plmr.pop();
        }
        chmin(ccur, rmax);
        cur += ccur * 2;
        chmin(ret, cur);
    }
    return ret;
}

signed main() {
    cin >> A >> B;
    N = A.length();
    vint Av(N), Bv(N * 3);
    rep(i, N) {
        Av[i] = A[i] == '1';
        Bv[i] = Bv[i + N] = Bv[i + N * 2] = B[i] == '1';
    }
    sort(all(B));
    if (B[0] == '0' && B[N - 1] == '0') {
        if (A == B) { cout << 0 << endl; }
        else { cout << -1 << endl; }
        return 0;
    }
    int ans = solve(Av, Bv);
    reverse(all(Av)), reverse(all(Bv));
    chmin(ans, solve(Av, Bv));
    cout << ans << endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

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

/// command for char arrays with spaces -> scanf(" %[^\n]", text);
 
////////////////////////// Solution starts below. //////////////////////////////

int main(){

	fastio;
    int n, r;
    cin >> n >> r;
    if(n >= 10) cout << r;
    else cout << r + 100*(10-n);
    cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define vint(a,n) vint a(n); rep(i, n) cin >> a[i];
#define vll(a,n) vll a(n); rep(i, n) cin >> a[i];
#define ALL(n) begin(n),end(n)
#define RALL(n) rbegin(n),rend(n)
#define MOD (1000000007)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
using vbool=vector<bool>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[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; }

int main()
{
    int n; cin >> n;
    vll f(2001, 0);
    f[3] = 1;
    f[4] = 1;
    f[5] = 1;
    FOR(i, 6, 2002){
        f[i] = 1;
        FOR(j, 3, i){
            f[i] += f[i - j];
            f[i] %= MOD;
        }
    }

    pr(f[n]);
    return 0;}

Measured memory_bytes: 3640
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;

int main()
{
	string str;
	cin>>str;
	vector<int> alphabet(26,0);
	for(int i = 0; i < str.length(); i++){
		int num = str[i] - 'a';
		alphabet[num]++;
	}
	bool ans = true;
	for(int i = 0; i < 26; i++){
		if( alphabet[i] % 2 != 0){
			ans = false;
			break;
		}
	}
	if( ans == true){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}



Measured memory_bytes: 3060
N, P = map(int, input().split())
A_list=map(int, input().split())
# N=7
# P=1
# A_list=[1,1,1,1,1,1,1]
count=len([A for A in A_list if int(A)%2==P])
if count==(N*(not P)):
    print((not P) * (2**N))
else:
    print(2**(N-1))

Measured memory_bytes: 3060
#include <iostream>
#include <vector>

using namespace std;

int calcCoins(int price) {
	const int coinNums[] = {500, 100, 50, 10, 5, 1};
	int result = 0;
	int remain = price;

	for (int i = 0; i < 6; i++) {
		int coinMaisu = remain / coinNums[i];
		result += coinMaisu;
		remain -= coinMaisu * coinNums[i];
	}

	return result;
}

int main(void){
    vector<int> prices;
	while (true) {
		int price;
		cin >> price;

		if (price == 0) break;
		prices.push_back(price);
	}

	for (int i = 0; i < prices.size(); i++) {
		cout << calcCoins(1000 - prices[i]) << endl;
	}
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  map<string, int> cnt;
  int n;
  cin>>n;
  int mcnt = 0;
  vector<string> ans;
  REP(i, n){
    string s;
    cin>>s;
    cnt[s]++;
    mcnt = max(mcnt, cnt[s]);
  }
  for(auto p:cnt){
    if(p.second == mcnt){
      ans.push_back(p.first);
    }
  }
  sort(ALL(ans));
  for(auto s:ans){
    cout<<s<<endl;
  }
  return 0;
}

Measured memory_bytes: 26868
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;

#define repi(i,a,b) for(ll i = (a); i < (b); i++)
#define rep(i, n) for(ll i = 0; i < (n); ++i)

int main() {
    int N;
    cin >> N;
    ll sum = 0;
    repi(i,1, N + 1) {
        if (i % 3 == 0 || i % 5 == 0) continue;
        sum += i;
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 3192
#include<stdio.h>
#include<iostream>
using namespace std;
int H,W,N,a[100005],Ans[105][105];
int main()
{
	int i,j,k=1;
	
	scanf("%d%d%d",&H,&W,&N);
	for(i=1;i<=N;i++)scanf("%d",&a[i]);
	
	for(i=1;i<=H;i++)
	{
		if(i&1)
		{
			for(j=1;j<=W;j++)
			{
				Ans[i][j]=k;
				a[k]--;
				if(a[k]==0)k++;
			}
		}
		else
		{
			for(j=W;j;j--)
			{
				Ans[i][j]=k;
				a[k]--;
				if(a[k]==0)k++;
			}
		}
	}
	
	for(i=1;i<=H;i++,putchar('\n'))
	for(j=1;j<=W;j++)printf("%d ",Ans[i][j]);
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    static public void main(String args[]){
        final int INF = (int)1e10;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[][] hapi = new long[n][3];

        long[][] dp = new long[n][3];
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < 3 ; j++) {
                hapi[i][j] = sc.nextLong();
                dp[i][j] = INF;
            }
        }
        for(int i = 0 ; i < 3 ; i++){
            dp[0][i] = hapi[0][i];
        }

        for(int i = 0 ; i < n-1 ; i++){
            for(int j = 0 ; j < 3 ; j++) {
                dp[i + 1][j] = Math.max(dp[i][(j+1)%3]+hapi[i+1][j], dp[i][(j+2)%3]+hapi[i+1][j]);
            }
        }

        long ans = Math.max(dp[n-1][0], Math.max(dp[n-1][1], dp[n-1][2]));
        System.out.println(ans);
    }
}


Measured memory_bytes: 105256
a,b = map(int,input().split())
S = input()
flag = 0
k = [str(i) for i in range(10)]
for i in range(len(S)):
  if i == a:
    if S[i] == "-":
      continue
    else:
      flag += 1
      print("No")
      break
  else:
    if S[i] in k:
      continue
    else:
      flag += 1
      print("No")
      break
if flag == 0:
  print("Yes")

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
i = 1
j = 1
l = []
while i<n:
    if a[i]==a[i-1]:
        l.append(a[i])
        i+=2
    else:
        i+=1
l.append(0)
l.append(0)
print(l[0]*l[1])

Measured memory_bytes: 58736
#include<iostream>
#include<algorithm>
#include<iomanip>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <new>
#include <cmath>
#include<fstream>
using namespace std;
#define Precision(i) cout << fixed << setprecision(i)
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
const ll N = 1e5 + 100, MOD = 1e9 + 7, INF = 1e15, SQ = 350, LOG = 20;
ll n, m, x1, x2, d, z , t, sum,y, y2, maxi,mini, ans, ptr, x, q, dp[N], a[N];
string s;
int main()  
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s;
	for (int i = 0; i < s.size(); i++) s[i] = (10 - (s[i] - '0')) + '0';
	cout << s;
}

Measured memory_bytes: 256
use std::io::stdin;

fn main() {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    let abc: Vec<_> = line.split_whitespace().collect();

    if abc.windows(2).all(|s2| s2[0].chars().last() == s2[1].chars().next()) {
        println!("YES");
    } else {
        println!("NO");
    }
}


Measured memory_bytes: 4352
n,m=map(int,input().split())
l=list(map(int,input().split()))
pre=0
for i in range(n):
    pre=(pre+l[i])%m
    l[i]=pre

from collections import Counter as co
c=co(l)
print(sum(i*(i-1)//2 for i in c.values())+(c[0] if 0 in c else 0))

Measured memory_bytes: 14696
#include <iostream>
#include <queue>

using namespace std;

int waiti[100];
int seat[17];

const int INIT = 0xffffff;

typedef struct MATI
{
	int id;
	int num;
	int eat;
} MATI;

int get_eat(int n)
{
	return 17 * (n%2) + 3 * (n%3) + 19;
}

int get_num(int n)
{
	if(n%5==1) return 5;
	else return 2;
}

int can_sit(int n)
{
	bool is_able = true;
	for(int i=0; i<=17-n; i++)
	{
		is_able = true;
		for(int j=0; j<n; j++)
		{
			if(seat[i+j] != 0)
			{
				is_able = false;
				break;
			}
		}
		
		if(is_able) return i;
	}
	
	return -1;
}

void refresh()
{
	for(int i=0; i<17; i++)
	{
		if(seat[i] != 0)
		{
			seat[i] = seat[i] - 1;
			
		}
	}
}

void solve()
{
	for(int i=0; i<17; i++)
	{
		seat[i] = 0;
	}
	
	queue<MATI> col;
	
	for(int i=0; i<1000; i++)
	{
		int current_time = i;
		refresh();
		
		if(current_time%5==0)
		{
			MATI m;
			m.id = current_time /5;
			m.num = get_num(m.id);
			m.eat = get_eat(m.id);
			col.push(m);
		}
		
		while(!col.empty())
		{
			MATI m = col.front();
			int setter = can_sit(m.num);
			if(setter != -1)
			{
				for(int j=0; j<m.num; j++)
				{
					seat[setter+j] = m.eat;
				}
				
				int wait_time = current_time - m.id * 5;
				waiti[m.id] = wait_time;
				if(m.id==99) return;
				col.pop();
			}
			else
			{
				break;
			}
		}
	}
}

int main(int argc, char** argv)
{
	int n;
	solve();
	
	while(cin >> n)
	{
		cout << waiti[n] << endl;
	}
}

Measured memory_bytes: 0
// 20151013
// ??????????????¬??????????????¶?????§?£???????




#include<stdio.h>




int main() {
  int a, b;
  int i;
  int divi; // ?????§??¬?´???°
  int denomi; // ????°???¬?????°
  int dai, syo, ire;




  /* ??????????????¨????´? */
  while (scanf("%d %d", &a, &b) != EOF) {



    /* ??¶?´??????? */
    if (a > 2000000000 && a <= 0 && b > 2000000000 && b <= 0) {
	break;
    }




    /** ?????§??¬?´???°????±??????? **/
    /*** ??§?°???¢?????? ****/
    dai = a > b ? a : b;
    syo = a < b ? a : b;




    /*** ?????????????????? ***/
    while (dai % syo != 0) {
      ire = dai;
      dai = syo;
      syo = ire % dai;
    }
    divi = syo;




    /** ????°???¬?????°????±??????? **/
    denomi = a * (b / divi); // ????????§???????????????????????????????????????????????????????????? !




    /* ?????? */
    printf("%d %d\n", divi, denomi);
  }




  /* ?????? */
  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(ll (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;

//
void solve(long long N, std::vector<long long> A){
    vec(B,N);
    rep(i,N){
        B[i]=A[i];
    }
    sort(all(A));
    ll max=A[N-1];
    ll max2=A[N-2];
    if(max==max2){
        rep(i,N){
            op(max);
        }
        return;
    }else{
        rep(i,N){
            if(B[i]==max){
                op(max2)
            }else{
                op(max)
            }
        }
        return;
    }
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


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

int solve(int n){
  int res = n;
  for(int i = 2 ; i*i <= n ; i++){
    if(n % i == 0){
      res -= res / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) res -= res / n;
  return res;
}

int main(){
  int n;

  cin >> n;
  cout << solve(n) << endl;

  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
using namespace atcoder;
using LL = long long;

int main(){
  int N, Q;
  cin >> N >> Q;
  fenwick_tree<LL> ft(N);
  rep(i,N){
    LL a;
    cin >> a;
    ft.add(i, a);
  }
  rep(i,Q){
    int t;
    cin >> t;
    if(t == 0){
      int p;
      LL x;
      cin >> p >> x;
      ft.add(p, x);
    }
    else{
      int l, r;
      cin >> l >> r;
      cout << ft.sum(l, r) << endl;
    }
  }
  
  return 0;
}

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

#define pb(s) push_back(s)
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PI 3.14159265358979323846264338327950L


typedef long long ll;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    string str;
    cin>>N>>str;
    int x=0;
    int ans=0;
    for(int i=0;i<str.size();++i){
        if(str[i]=='I'){
            x+=1;
            ans=max(ans,x);
        }
        else{
            x-=1;
            ans=max(ans,x);
        }
    }
    cout<<ans;
    return 0;
}


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

using namespace std;

const int MAXN = 3e3 + 10;

int n, a[MAXN];
long long dp[MAXN][MAXN];

int main () {
	ios::sync_with_stdio(0), cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		dp[i][i] = a[i];
	}

	for (int di = 1; di < n; ++di)
		for (int i = 0; i < (n - di); ++i)
			dp[i][i + di] = max((a[i] - dp[i + 1][i + di]),
				 						(a[i + di] - dp[i][i + di -1]));

	--n;
	cout << dp[0][n] << '\n';
	
	return 0;
}


Measured memory_bytes: 70016
use proconio::input;

fn solve(n: i32, _m: i32, a: Vec<i32>) -> i32 {
    let x: i32 = a.iter().sum();
    if x <= n {
        n - x
    } else {
        -1
    }
}

fn main() {
    input! {
        n: i32,
        m: i32,
        a: [i32; m],
    }
    let r = solve(n, m, a);
    println!("{}", r);
}


Measured memory_bytes: 2208
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
const int MAX_N =200;
int n;
int cost[MAX_N][MAX_N];
bool visit[MAX_N];
int mincost[MAX_N]={INF};
int prime(){
	//memset(mincost, INF, sizeof(mincost));
	memset(visit, false, sizeof(visit));
	int res = 0;
	mincost[0]=0;
	/*rep(i, n){
		cout <<mincost[i];
		cout <<endl;
	}
	cout <<endl;*/
	while(1){
		int v = -1;
		for(int u =0; u <n;u++){
			if(!visit[u]&&(v==-1||mincost[u] < mincost[v])){
				v =u;
			}
		}
		if(v==-1)break;
		//cout <<"v = "<<v<<endl;
		visit[v]=true;
		res +=mincost[v];
		//cout <<res<<endl;
		for(int u =0;u <n ;u++){
			mincost[u]=min(mincost[u],cost[v][u]);
		}
	}
	//cout <<res<<endl;
	return res;
}

int main(){
	cin>>n;
	for(int i =0;i < n;i++){
		mincost[i]=INF;
		for(int j =0;j < n;j++){
			int x;
			cin>>x;
			if(x==-1){
				cost[i][j]=INF;
			}else{
				cost[i][j]=x;
			}
		}
	}
	/*rep(i, n){
		rep(j, n){
			printf("%10d",cost[i][j]);
		}
		cout <<endl;
	}*/

	cout <<prime()<<endl;
	return 0;
}

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

int W,H,w,h;

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	H=read();W=read();h=read();w=read();
	if (H%h==0&&W%w==0) printf("No\n");
	else {
		printf("Yes\n");
		for (int i=1;i<=H;i++)
			for (int j=1;j<=W;j++)
				printf((j!=W)?"%d ":"%d\n",(i%h==0&&j%w==0)?-1000*(w*h-1)-1:1000);
	}
	return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>

using namespace std;

int main() {
  int N;
  cin >> N;

  vector<long> x(N);
  vector<long> y(N);
  vector<long> h(N);

  int tmpX, tmpY, tmpH;
  for (int i=0; i<N; i++) {
    cin >> x[i] >> y[i] >> h[i];
    if (h[i] > 0) {
      tmpX = x[i];
      tmpY = y[i];
      tmpH = h[i];
    }
  }

  int X=0, Y=0;
  for (int i=0; i<=100; i++) {
    for (int j=0; j<=100; j++) {
      long H = tmpH + abs(i - tmpX) + abs(j - tmpY);
      H = max(H, 0L);
      bool f = true;


      for (int k=0; k<N; k++) {
        long tmp = H - abs(i - x[k]) - abs(j - y[k]);
        tmp = max(tmp, 0L);

        if (tmp != h[k]) f = false; 
      }

      if (f) {
        cout << i << " " << j << " " << H << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] a = new int[n];
        int ans = (int)Math.pow(3,n);
        int count = 1;
        
        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
            if(a[i]%2==0){
                count=count*2;
            }
        }
        
        System.out.println(ans-count);
   }
}


Measured memory_bytes: 35668
//#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cctype>
#include <cstdlib>      // srand,rand


using namespace std;
#define modd 1000000007



typedef pair<long long, long long> pl;


typedef string::const_iterator State;
class ParseError {};




#define ll long long




class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};


class SegmentTree {
private:
	int n;
	vector <ll> node;

public:
	// 元の配列　v をセグメントツリーで表現する。
	SegmentTree(vector<ll> v) {
		//最下段のノード数は元配列のサイズ以上になる最小の2冪->これをnとおく。
		//セグ木全体で必要なノード数は2n-1個である。
		int sz = v.size();
		n = 1; 
		while (n < sz)n *= 2;

	}

};




long long N, M, K, a, b, c, d, e, H, W, L,T;
ll A[300005] = {};
ll B[300005] = {};
ll C[100][3005] = {};
bool f, ff;
string S,SS;
set <long long>sll;
pl bufpl;
vector <long long>vl[100005];
vector <long long>vll;
vector <pl>vpl;
vector <string> vs;
set<ll> llset[50];
multiset<ll> llmset;
queue<ll> ql;


struct ST
{
	ll first;
	ll second;
	ll kaisuu;
	

	bool operator<(const ST& another) const
	{
		return first < another.first;//比較
	};

};



/*vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}


ll minn, maxx;
double ansa;

ll zettai(ll aa) {

	if (aa < 0) {
		aa *= -1;
	}
	return aa;

}


bool itta[300000];

int main() {
	
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = A[i];
	}

	a = 0;
	b = 1;
	c = 0;
	d = 0;
	for (int i = 0; i < N; i++) {
		a += A[i];
		if (b > 0) {
			if (a <= 0) {
				c += b - a;
				a = b;
			}
		}
		else {
			if (a >= 0) {
				c += a-b;
				a = b;
			}
		}

		b *= -1;
	}

	a = 0;
	b = 1;

	for (int i = 0; i < N; i++) {


		b *= -1;
		a += A[i];
		if (b > 0) {
			if (a <= 0) {
				d += b - a;
				a = b;
			}
		}
		else {
			if (a >= 0) {
				d += a - b;
				a = b;
			}
		}

	}

	cout << min(c, d) << endl;

	//cout << fixed << setprecision(10) << ansa << endl;
	return 0;



}


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

int main() {
    int A,B,C,D,L,R;
    cin >> A >> B >> C >> D;
    L = A + B;
    R = C + D;
    if (L > R) cout << "Left";
    else if (L == R) cout << "Balanced";
    else cout << "Right";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <random>
#include <chrono>
#include <algorithm>
 
uint64_t mod = 1000 * 1000 * 1000 + 7;
static int pow(uint64_t x, uint64_t n){
	uint64_t ans=1;
	while(n){
		if(n%2){
			ans *= x;
			ans %= mod;
			n-=1;
		}
		x *= x;
		x %= mod;
		n/=2;
	}
	return ans;
}
int main(void){
	uint64_t n, m, k;
	std::cin >> n >> m >> k;
	uint64_t sq = n * m;
	uint64_t combination = 1;
	uint64_t x = 0;
	for(int i=1;i<n;i++){
		x+=m * m * (n-i)*i;
		x %=mod;
	}
	for(int i=1;i<m;i++){
		x+=n*n*(m-i)*i;
		x %= mod;
	}
	uint64_t C = 1, O=1, M=1;
	for(int i=1;i<=n*m-2;i++){
		C *= i;
		C %= mod;
	}
	for(int i=1;i<=k-2;i++){
		O*=i;
		O %= mod;
	}
	O = pow(O, mod - 2);
	for(int i=1;i<=n*m - k;i++){
		M *= i;
		M %= mod;
	}
	M = pow(M, mod - 2);
	x*=C;
	x %= mod;
	x*= O;
	x %= mod;
	x*= M;
	x %= mod;
	std::cout << x << std::endl;
}


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

typedef long long lint;
typedef long double louble;

const char lf = '\n';

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	template<typename T> inline int ts(T *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		s[a]=0;
		return a;
	}
}
using ae86::ty;
using ae86::ts;

const int _ = 3007 , __ = _<<1;

int n,nn,s[__];
int rk[__]={0},loc[2][_]={0};
string f[__];

inline string fuck(int l,int r)
{
	string ret="";
	for(int i=1;i<=nn;i++)if(l<=rk[i] && rk[i]<=r)ret.push_back(s[i]+'a');
	return ret;
}

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	n=ty(),nn=n+n,ts(s+1);
	for(int i=1,temp[2]={0};i<=nn;i++)s[i]-='a',temp[s[i]]++,rk[i]=temp[s[i]],loc[s[i]][temp[s[i]]]=i;

	f[n+1]="";
	for(int i=n;i>=1;i--)
	{
		f[i]=f[i+1];
		if(loc[0][i]<loc[1][i])
		{
			int j=i;
			while(j<=n && loc[0][j]<loc[1][i])j++;
			f[i]=max(f[i],"ab"+f[j]);
		}
		else
		{
			int j=i+1;
			while(j<=n && loc[1][j]<loc[0][j-1])j++;
			f[i]=max(f[i],fuck(i,j-1)+f[j]);
		}
	}
	cout<<f[1]<<lf;

	return 0;
}


Measured memory_bytes: 14720
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

#include<bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

#define int         long long
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>

#define all(a)      (a).begin(),(a).end()
#define FF           first
#define SS           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell          1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
// mp::cpp_int
#define pp pair<int,int>


int solve( ){

int n;
vi a;
cin>>n;
rep(i,1,n+1)
{
  int x;
  cin>>x;
  a.pb(x);
}
vi v;
 rep(i,0,n)
 {
    if(a[i]-1>v.size()){cout<<-1;return 0;}
    v.insert(v.begin()+a[i]-1,a[i]);
 }
rep(i,0,n)
cout<<v[i]<<endl;
return 0;
}



signed main()
{  int t=1;
 ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
  

  
  clock_t time_req;

    // Without using pow function
    time_req = clock();
    
//cin>>t;
    int k=1;
   while(t--)
     {
       //cout<<"case #"<<k<<":"<<" ";k++;
      solve();
     }

         time_req = clock() - time_req;
   //cout << "Processor time taken is "
     // << (double)time_req/CLOCKS_PER_SEC << " seconds" << endl;


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

struct less1 {
  bool operator()(const pair<li,li>& p1, const pair<li,li>& p2) const{
    return p1.first+p1.second<p2.first+p2.second;
  }
};
struct less2 {
  bool operator()(const pair<li,li>& p1, const pair<li,li>& p2) const{
    return p1.second-p1.first<p2.second-p2.first;
  }
};

int main(){
  set<pair<li,li>,less1> sl1;
  set<pair<li,li>,less2> sl2;
  int n; cin >>n;
  rep(i,n){
    li x,y; cin >>x >>y;
    sl1.insert({x,y});
    sl2.insert({x,y});
  }
  auto itr1=sl1.begin(),itr2=sl1.end();
  itr2--;
  li ans=(itr2->first+itr2->second)-(itr1->first+itr1->second);
  if(df)print(ans);
  itr1=sl2.begin();itr2=sl2.end();
  itr2--;
  li a2=(itr2->second-itr2->first)-(itr1->second-itr1->first);
  if(df)print(a2);
  ans=max(ans,a2);

  print(ans);
}



Measured memory_bytes: 28596
#include <bits/stdc++.h>
#define MOD 1000000007
#define pb push_back
typedef long long ll;
using namespace std;

ll N, W;
vector<ll> w, v; 
ll dp[100005][105];

ll bt(ll rem,  ll idx){
    if(rem < 0){
        return -1*INT_MAX;
    }
    if(rem == 0){
        return dp[rem][idx] = 0; 
    }

    if(idx == N ){
        return dp[rem][idx] = 0; 
    }
    if(dp[rem][idx] != -1){
        return dp[rem][idx];
    }

    ll ans  = 0;

    if(w[idx] > rem){
        ans = bt(rem, idx+1);
    }
    else{
        ans = max(v[idx]+bt(rem-w[idx],  idx+1), bt(rem, idx+1));
    }

    dp[rem][idx] = ans;
    return dp[rem][idx];
}

 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp, -1, sizeof dp);
    cin>>N>>W;
    ll t1, t2;
    for (int i = 0; i < N; ++i)
    {
        cin>>t1>>t2;
        w.pb(t1), v.pb(t2);
    }
    ll a1 = bt(W,0);
    cout<<a1<<"\n";

}

Measured memory_bytes: 82304
d,g=map(int,input().split())
p=[0]*d
c=[0]*d

ans=10**9
for i in range(d):
    p[i],c[i]=map(int,input().split())
    
for i in range(2**d):
    score=0
    cnt=0
    com=-1
    for j in range(d):
        if ((i >> j) & 1):
            score+=100*(j+1)*p[j]+c[j]
            cnt+=p[j]
        else:
            com=j
 
    flg=0
    if score<g and com>=0:
        while p[com]>flg:
            score+=100*(com+1)
            flg+=1
            if score>=g:
                break
    if score>=g:
        cnt+=flg
        if ans>cnt:
            ans=cnt

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll solve() {
    ll N, A, B;
    cin >> N >> A >> B;
    ll ans = 0;
    if ( A > B ) return 0;
    if ( N == 1 && A != B ) return 0;
    if ( N == 1 ) return 1;
    else {
        return  (B*(N-1)+A) - (B+A*(N-1)) + 1;
    }
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  string S,T;
  cin>>S;
  T=S[S.size()-1];
  rep(i,S.size()-1) T+=S[S.size()-2-i];
  string SS;
  SS=S[0];
  int ans=0,c=0;
  string TT;
  TT=T[0];
  int ans2=0,c2=0;
  if(S.size()==1) cout<<1<<endl;
  else{
    rep(i,S.size()-1){
      if(i){
        if(SS.size()>1||SS[0]!=S[i]) SS=S[i];
        else{
          SS=S[i];
          SS+=S[++i];
        }
        c=i;
      }
      ans++;
    }
    if(c==S.size()-2&&SS.size()!=1||S[S.size()-2]!=S[S.size()-1]) ans++;
    rep(i,T.size()-1){
      if(i){
        if(TT.size()>1||TT[0]!=T[i]) TT=T[i];
        else{
          TT=T[i];
          TT+=T[++i];
        }
        c2=i;
      }
      ans2++;
    }
    if(c2==T.size()-2&&TT.size()!=1||T[T.size()-2]!=T[T.size()-1]) ans2++;
    cout<<min(ans,ans2)<<endl;
  }
}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()


int main() {
	int n;
	cin >> n;
	vector<int> a(21);
	FOR(i, 1, n) {
		cin >> a[i];
	}
	int cnt = 0;
	FOR(i, 1, n - 2) {
		if (max({ a[i],a[i + 1], a[i + 2] }) != a[i + 1] && min({ a[i],a[i + 1], a[i + 2] }) != a[i + 1]) {
			cnt++;
		}
	}
	pv(cnt)
	return(0);
}

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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
int main()
{
    int n;cin >> n;
    vector<int> a(n);rep(i,n)cin >> a[i];
    int txor = 0;
    rep(i,n)
    {
       txor = txor^a[i];
    }
    rep(i,n)
    {
        cout << (txor^a[i]) << " ";
    }
    cout  << endl;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<tup> city(m);
    rep(i,m) {
        int p, y;
        cin >> p >> y;
        city.at(i) = make_tuple(i, p, y);
    }
    sort(city.begin(), city.end(), [](tup x, tup y) {
        if (get<1>(x) == get<1>(y)) return get<2>(x) < get<2>(y);
        return get<1>(x) < get<1>(y);
    });
    vector<string> ans(m);
    int p = 0, id = 0;
    rep(i,m) {
        if (p == get<1>(city.at(i))) id++;
        else id = 1;
        p = get<1>(city.at(i));
        ostringstream pss, idss;
        pss << setfill('0') << setw(6) << p;
        idss << setfill('0') << setw(6) << id;
        ans.at(get<0>(city.at(i))) = pss.str() + idss.str();
    }
    rep(i,m) cout << ans.at(i) << endl;
    return 0;
}

Measured memory_bytes: 7484
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct SideLine{
  int h, w, ru, rl, lu, ll;
};

int N, M, H, K;
int g[1024][1024], s[1024], score[1024];
SideLine SL[100001];

int simulate(int n){
  int cur = n, h = 0;
  while(h <= H){
    //    cout << h << " " << cur << " " << g[h][cur]<< endl;
    if(g[h][cur]!=-1){ SL[g[h][cur]].lu = n; cur++; }
    else if(cur > 0 && g[h][cur-1]!=-1){ SL[g[h][cur-1]].ru = n; cur--; }
    h++;
  }
  return s[cur];
}

int del(int lb, int rb, int m){
  int res = 0;
  SideLine sl = SL[m];
  if(lb <= sl.ru && sl.ru <= rb && lb <= sl.lu && sl.lu <= rb){    
  }else if(lb <= sl.ru && sl.ru <= rb){
    res += score[sl.lu] - score[sl.ru];
  }else if(lb <= sl.lu && sl.lu <= rb){
    res += score[sl.ru] - score[sl.lu];
  }
  return res;
}

int main(){
  while(scanf("%d%d%d%d", &N, &M, &H, &K) && (N + M + H + K)){
    rep(i, N) scanf("%d", s+i);
    int a, b;

    memset(g, -1, sizeof(g));
    rep(i, M){
      SideLine &sl = SL[i];
      scanf("%d%d", &a, &b); a--; 
      g[b][a] = i;
      sl.h = b; sl.w = a;
    }

    /*    rep(i,H){
      rep(j, N) cout << g[i][j] << " ";
      cout << endl;
      }*/
    rep(i, N){
      score[i] = simulate(i);
      //      cout << i << " " << score[i] << endl;
    }
    
    int res = INF, sum = 0;
    rep(i, K) sum += score[i];
    res = min(res, sum);
    //    cout << sum << endl;
    rep(i, M) res = min(res, del(0, K-1, i)+sum);
    /*    for(int i = K; i < N; i++){
      sum -= score[i-K];
      sum += score[i];
      res = min(res, sum);
      cout << sum << endl;
      rep(j, M){ res = min(res, del(i-K+1, i, j)+sum);}// cout << del(i-K+1, i, j)+sum << endl; }
      }*/
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 7644
(N, M), *miti = [[*map(int, line.split())] for line in open(0)]

# print(miti)

A = [list() for _ in range(N+1)]
for m in miti:
    a, b = m
    A[a].append(b)
    A[b].append(a)

# print(A)

ans = [0] * (N + 1)
dist = [N] * (N + 1)
R = [list() for _ in range(N)]

dist[1] = 0
R[0].append(1)
ans[1] = 88888
for i in range(N):
    for p in R[i]:
        for t in A[p]:
            if i + 1 < dist[t]:
                dist[t] = i + 1
                R[i+1].append(t)
                ans[t] = p

dist = dist[1:]
ans = ans[2:]
if all(d < N for d in dist):
    print("Yes")
    for a in ans:
        print(a)
else:
    print("No")

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

// ただのunion find が使いたいばあい
struct UnionFind {
    vector<long long> par; // 親ノード
    vector<long long> rank; // ランク
    vector<long long> root_size; //ノードが根のときに、何個の子要素を持っているのか。(自分を含む)
                            //親じゃない場合は-1を出力

    UnionFind(long long n = 1) {
        init(n);
    }

    void init(long long n = 1) {
        par.resize(n); rank.resize(n); root_size.resize(n);
        for (long long i = 0; i < n; ++i) par[i] = i, rank[i] = 0, root_size[i] = 1;
    }

    long long root(long long x) {
        if (par[x] == x) {
            return x;
        }
        else {
            long long r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(long long x, long long y) {
        return root(x) == root(y);
    }

    //yをxにマージ
    bool merge(long long x, long long y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        root_size[x] += root_size[y];
        root_size[y] = -1;
        return true;
    }

    long long size(long long x){
        x = root(x);
        return root_size[x];
    }
};



int main(){
    int N, M;
    cin >> N >> M;
    UnionFind UF(N);

    for(int i=0; i<M; ++i){
        int A, B;
        cin >> A >> B;
        A--; B--;
        UF.merge(A, B);
    }

    for(int i=0; i<N; ++i){
        UF.root(i);
    }

    map<int, int> s;

    for(int i=0; i<N; ++i){
        if(s.count(UF.root(i)) == 0 ){
            s[UF.root(i)] = 1;
        }else{
            s[UF.root(i)]++;
        }
    }

    int res = 0;
    for(auto p : s){
        res = max(res, p.second);
    }


    cout << res << endl;

}

Measured memory_bytes: 17056
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())

    Q = [[] for _ in range(N - 1)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[a - 1].append(b - 2)

    min_y = INF
    ans = 0
    for i, ys in enumerate(Q):
        if ys:
            min_y = min(min_y, min(ys))
        if i == min_y:
            ans += 1
            min_y = INF

    print(ans)
    return


if __name__ == '__main__':
    main()


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

int main(){

    while(1){
        int n;
        cin >> n;
        vector<int> a(n);
        if(n==0)break;
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        string s;
        cin >> s;
        string al="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string ans="";
        for(int i=0;i<s.size();i++){
            for(int j=(int)al.size()-1;j>50;j--){
                if(s[i]==al[j]){
                    ans+=al[j-a[i%n]];
                    break;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}


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

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;
const long long INF = 1LL << 60;

signed main()
{

    int a, b, c, k;
    cin >> a >> b >> c >> k;
    bool ans = false;
    int cnt = 0;

    while (a >= b)
    {
        b *= 2;
        cnt++;
    }
    while (b >= c)
    {
        c *= 2;
        cnt++;
    }

    if (cnt <= k)
    {
        print("Yes");
    }
    else
    {
        print("No");
    }

    return 0;
}


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

using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;
    ll N = S.size();
    ll ans = 0;
    ll sum = 0;

    bool check = 1;

    for(ll i = 0; i < N; i++) {
        if(S.at(i) == 'W') {
            ans += i;
            sum++;
        }
    }
    cout << ans - sum*(sum - 1)/2 << endl;
    return 0;

    while(0) {
        check = 0;
        for(ll i = 0; i < N - 1; i++) {
            if(S.at(i) == 'B' && S.at(i + 1) == 'W') {
                S.at(i) = 'W';
                S.at(i + 1) = 'B';
                check = 1;
                ans++;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define r(i,a,n) for(int i=a;i<n;i++)
using namespace std;
int main(){
  priority_queue<int>q;
  while(1){
    string s;int a;
    cin>>s;
    if(s[2]=='s'){
      cin>>a;
      q.push(a);
    }
    else if(s[2]=='t'){
      cout<<q.top()<<endl;
      q.pop();
    }
    else break;
  }
}

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

const int mN = 200200;
int c[mN];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i=2, a; i<=n; i++) cin >> a, c[a]++;
	for (int i=1; i<=n; i++) cout << c[i] << " ";
}

Measured memory_bytes: 4400
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long n;
	int p,c,m=0,s[100];
	cin>>n;
	cin>>p;
	while (n!=0)
	{
		c=n%p;
		n=n/p;
		m++;s[m]=c;  
	}

	cout<<m;
 
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main()
{
  char s[200001];
  int i;
  int n;
  int a,b,c;
  scanf("%s",s);
  n=strlen(s);
  for(i=0;i<n;i++){
    if(s[i]=='A'){
      a=i;
      break;
    }
  }
  for(i=0;i<n;i++){
    if(s[i]=='Z'){
      b=i;
    }
  }
  printf("%d",b-a+1);
  return 0;
}


Measured memory_bytes: 1928
s=gets.chomp
s0=""
s1=""
fl=false
q=gets.to_i
q.times do
  qu=gets.chomp
  if qu=="1"
    fl=!fl
  else
    if fl&&qu[2]=="1"||!fl&&qu[2]=="2"
      s1 << qu[4]
    else
      s0 << qu[4]
    end
  end
end
if !fl
  puts s0.reverse+s+s1
else
  puts s1.reverse+s.reverse+s0
end



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

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e6+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int N;
string s;

struct INT{int i = -1;};

map<pair<string, string>, INT> dp;

string s1, s2;
int dfs(int i){
    auto &res = dp[{s1, s2}].i;
    if(res != -1) { return res;}
    if(i == 2*N) {
        FOR(j, 0, N) if(s1[j] != s2[N-1-j]) return res = 0;
        return res = 1;
    }
    if(i > N){
        int l = N - s2.size();
        int r = s1.size();
        FOR(i, l, r){
            if(s1[i] != s2[s2.size()-1-i+l]) return res = 0;
        }
    }
    res = 0;
    s1.pb(s[i]);
    res += dfs(i+1);
    s1.pop_back();
    s2.pb(s[i]);
    res += dfs(i+1);
    s2.pop_back();
    return res;
}

signed main(){
    fast_io();
    cin >> N >> s;
    cout << dfs(0) << endl;
}

/*
18
abbaccddeffeghghijjikllkmmnnopqqporr
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*/

Measured memory_bytes: 380672
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using Int = boost::multiprecision::cpp_int;
int main() {
    Int H, W;
    cin >> H >> W;
    if (H == 1 || W == 1) cout << 1 << endl;
    else if (H * W % 2 == 0) cout << H * W / 2 << endl;
    else cout << H * W / 2 + 1 << endl;
}


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

long long GCD(long long x, long long y) {
    return y ? GCD(y, x%y) : x;
}

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  for(int i=0; i<n; i++){
    cin >> vec[i];
  }
  int ans = vec[0];
  for(int i=1; i<n; i++){
    ans = GCD(ans, vec[i]);
  }
  cout << ans << endl;
  return 0;
}
    

Measured memory_bytes: 3752