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

using namespace std;

long long a, s;
int res = 1e9;

int calc(long long x){
	int ans = 0;
	while(x){
		ans ++;
		x /= 10;
	}
	return ans;
}

int main(){
	cin >> a;
	s = sqrt(a);
	for(int i = 1; i <= s; i ++){
		if(a%i == 0){
			res = min(res, max(calc(a/i), calc(i)));
		}
	}
	printf("%d", res);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#define io ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll a[maxn],pre[maxn];//,sum[maxn];
const int mod=1e9+7;
void solve(){
     int n;cin>>n;
    //ll sum=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    //sort(a+1,a+1+n);
    //pre[0]=0;
    for(int i=1;i<=n;i++){pre[i]=pre[i-1]+a[i];}
    ll ans=0;
    for(int i=1;i<n;i++){
        ans=(ans+((pre[n]-pre[i])%mod)*a[i]%mod)%mod;
    }
    cout<<ans%mod;
}
int main(){
    io;
    //int T;cin>>T;
    //while(T--)
        solve();
}


Measured memory_bytes: 6280
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    string s;
    cin >> s;
    cout << s.substr(0,3) << endl;
}


Measured memory_bytes: 3656
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n, m;
    cin >> n >> m;

    ll maL = 0, miR = INF;
    rep(i, m) {
        ll L, R;
        cin >> L >> R;
        chmax(maL, L);
        chmin(miR, R);
    }
    
    out(max(0LL, miR - maL + 1));
    re0;
}

Measured memory_bytes: 256
//Author : pakhandi
//
using namespace std;

#include <bits/stdc++.h>

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

#define IGNORE cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');

const ll INF = (1LL << 58);

#ifdef BUGGY
	bool DEBUG = 1;
#endif
#ifndef BUGGY
	bool DEBUG = 0;
#endif



int main()
{
	ll A, B;
	 cin >> A >> B;

	int ans = 0;

	for (ll i = 1; i <= 3; i++) {
		if ((A * B * i) % 2) {
			ans = 1;
		}
	}

	if (ans) {
		cout << "Yes";
	} else {
		cout << "No";
	}

	return 0;
}
/*
	Powered by Buggy Plugin
*/

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        String a = inp.next();
        String b = inp.next();
        inp.close();
        if (a.equals("H")) {
            System.out.println(b);
        }
        else {
            System.out.println(b.equals("D") ? "H" : "D");
        }
    }
}

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

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)

int c[10][1005];
const int INF = 10001000;

int main(){
    int h, w, k;
    cin >> h >> w >> k;
    string s[h];
    rep(i,h) cin >> s[i];

    long long ans = INF;

    rep(div,1<<(h-1)) {
        int g = 0;
        int id[h];
        rep(i, h) {
            id[i] = g;
            if (div>>i&1 == 1) ++g;
        }
        // --- ここまでで 横にg回切ってる

        rep(i,h)rep(j,w) c[i][j] = 0;
        rep(i,h)rep(j,w) c[id[i]][j] += (s[i][j] == '0'? 0:1);
        // --- 横に分断された結果の g+1個のブロック

        long long num = g;
        // 各ブロックごとの暫定和
        vector<int> now(g+1);
        auto add = [&](int j) {
            rep(i,g+1) now[i] += c[i][j];
            rep(i,g+1) if(now[i] > k) return false;
            return true;    
        };

        rep(j,w) {
            if (!add(j)) {
                ++num;
                now = vector<int>(g+1);
                if(!add(j)) {
                    num = INF;
                    break;
                }
            }
        }

        ans = min(ans, num);
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def search(c,a,b):
    r={'o':'x','x':'o'}
    ans=0
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            ans+=max(abs(y-a),abs(x-b))

    return ans

def mami():
    m=0
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('o',i,j)
                if t>m:
                    m=t
                    a,b=i,j
    return(a,b)

def char():
    m=1
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('x',i,j)
                if t>=m:
                    m=t
                    a,b=i,j
    return(a,b)

def rev(c,a,b):
    #s[a][b]=c
    r={'o':'x','x':'o'}
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            #i,j=direct[d]
            y,x=a+i,b+j
            while s[y][x]==r[c]:
                s[y][x]=c
                y+=i
                x+=j
    s[a][b]=c

s=[['.']*10]
for _ in range(8):
    s.append(['.']+list(input())+['.'])
s=tuple(s+[['.']*10])

while 1:
    a,b=mami()
    if a>0:
        rev('o',a,b)
    c,d=char()
    if c>0:
        rev('x',c,d)
    if all(i==-1for i in(a,b,c,d)):
        break
for t in s[1:-1]:
    print(*t[1:9],sep='')


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

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{
  ll m;
  cin>>m;


  cout<<48-m<<endl;
  return 0;
}


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

int INF = 1000000007;

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> c(10, vector<int>(10));
	rep(i, 10) {
		rep(j, 10) {
			cin >> c[i][j];
		}
	}
	vector<vector<int>> m(h, vector<int>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> m[i][j];
		}
	}
	vector<int> v = { 0,1,2,3,4,5,6,7,8,9 };
	vector<int> mincost(10, INF);
	do {
		int i = 0;
		int cnt = 0;
		while (v[i] != 1) {
			cnt += c[v[i]][v[i + 1]];
			i++;
		}
		mincost[v[0]] = min(mincost[v[0]], cnt);
	} while (next_permutation(v.begin(), v.end()));
	int ans = 0;
	rep(i, h) {
		rep(j, w) {
			ans += mincost[m[i][j]];
		}
	}
	cout << ans << endl;
}

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

int main()
{
    int n, a[20][31], b[30];
    string str[20];

    while( cin >> n )
    {
        if( !n )
            break;

        for( int i = 0; i < 20; i++ )
            for( int j = 0; j < 31; j++ )
                a[i][j] = 0;

        for( int i = 0; i < 30; i++ )
            b[i] = 0;

        for( int i = 0; i < n; i++ )
        {
            cin >> str[i];
            cin >> a[i][0];
            for( int j = 1; j <= a[i][0]; j++ )
            {
                cin >> a[i][j];
                b[a[i][j]]++;
            }
        }

        string res;
        int min = 100000;
        for( int i = 0; i < n; i++ )
        {
            int sum = 0;
            for( int j = 1; j <= a[i][0]; j++ )
                sum += n + 1 - b[a[i][j]];
            if( min > sum )
            {
                res = str[i];
                min = sum;
            }
            else if( min == sum )
                if( str[i] < res )
                    res = str[i];
            else;
        }
        cout << min << " " << res << endl;
    }

    return 0;
}


Measured memory_bytes: 3184
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    string s; cin >> s;
    int aa = 0, bb = 0, cc = 0;
    REP(i, 0, s.size()){
        if(s[i] == 'a'){
            aa++;
        }else if(s[i] == 'b'){
            bb++;
        }else{
            cc++;
        }
    }
    int m = max({aa,  bb, cc});
    int mi = min({aa, bb, cc});
    if(m - mi <= 1){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

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

int main() {
    int n,k;string s;
    cin>>n>>k>>s;
    vector<int> a;
    a.push_back(0);
    int c=1;
    for (int i=0;i<n;i++) {
        if (i==n-1)
            a.push_back(a.back()+c);
        else if (s[i]==s[i+1])
            c++;
        else {
            a.push_back(a.back()+c);
            c=1;
        }
    }
    int mx=0;
    if (s[0]=='0')
        mx=max(mx,a[min(2*k,(int)a.size()-1)]-a[0]);
    for (int i=s[0]=='0';i<a.size();i+=2)
        mx=max(mx,a[min(i+2*k+1,(int)a.size()-1)]-a[i]);
    cout<<mx<<endl;
    return 0;
}

Measured memory_bytes: 1020
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n+1];
		int[] b = new int[n+1];
		int count = 0;
		int ans = 0;
		a[0] = 0;
		for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
		for (int i = n; i >= 1; i--) {
			for (int j = 2; j*i <= n; j++) {
				if(b[i*j]==1) count++;
			}
			if(count%2!=a[i]) {
				b[i] = 1;
				ans++;
			}
			count = 0;
		}
		System.out.println(ans);
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			if(b[i] == 1) sb.append(String.valueOf(i)+' ');
		}
		System.out.println(new String(sb));
	}
}


Measured memory_bytes: 72040
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n,k] <- getIntList
    ass <- replicateM k $ do
        getLine
        as <- getIntList
        return as
    print . length . filter (==1) . map length . group . sort $ [1..n] ++ (concat ass)

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

int main () {
    int n, d;
    cin >> n >> d;
    d *= 2;
    d += 1;
    if (n % d == 0) {
        cout << n / d;
    }
    else {
        cout << n / d + 1;
    }
}


Measured memory_bytes: 256
class Inning
  attr_accessor :score, :base, :out

  def initialize()
    @score, @out = 0, 0
    @base = [0, 0, 0]
  end

  def solve(str)
    case str
    when 'HIT'
      if i = @base.index(0)
        @base[i] = 1
      else
        @score += 1
      end
    when 'OUT'
      @out += 1
    when 'HOMERUN'
      @score += @base.inject(0) {|s, x| s + x} + 1
      @base.fill(0)
    end
  end
end

times = 0
num = gets.to_i

while times < num
  t = Inning.new()
  while t.out < 3
    str = gets.chomp!
    t.solve(str)
  end
  puts t.score
  times += 1
end

Measured memory_bytes: 2360
#include<iostream>
#include <algorithm>
#include<map>
using namespace std;
int arr1[10000005];
long long  solveitabdo(long long x)
{
	for (long long i = 1; i <= x; i++)
	{
		for (long long j = i; j <= x; j += i)
		{
			arr1[j]++;
		}
	}
	long long back1 = 0;
	for (long long i = 1; i <= x; i++)
	{
		back1 += arr1[i] * i;
	}
	return back1;
}
int main()
{
	long long x;
	cin >> x ;
	cout<<solveitabdo(x);
}


Measured memory_bytes: 42648
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];
        for(int i = 0; i < n; i++){
            p[i] = sc.nextInt();
        }
        int min = p[0];
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(min >= p[i]){
                ans++;
            }
            min = Math.min(min,p[i]);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 64612
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define fi first
#define sc second
#define mp make_pair
typedef pair<int,int> P;
typedef pair<int,P> Q;
typedef pair<double,Q> R;

P pos[2000005];
int m,n;
int dp[1000005];
bool pr[1000005];
bool ex[4005][4005];
int val[4005][4005];

int main(){
	int dx[4]={0,-1,0,1};
	int dy[4]={1,0,-1,0};
	pos[1] = mp(2000,2000);
	int cur = 2;
	int d = 0;
	int len = 1;
	for(int i=0;cur < 1100000;i++){
		for(int j=0;j<len;j++){
			pos[cur] = pos[cur-1];
			pos[cur].fi += dx[d];
			pos[cur].sc += dy[d];
			cur ++;
		}
		d = (d+1)%4;
		if(i%2 == 1) len++;
	}
	for(int i=1;i<=1000000;i++) val[pos[i].fi][pos[i].sc] = i;
	pr[1] = 1;
	for(int i=2;i<=1000000;i++){
		if(pr[i]) continue;
		for(int j=2;j*i<=1000000;j++) pr[i*j] = 1;
	}
	
	while(1){
		cin >> m >> n; if(m == 0) return 0;
		rep(i,1000005) dp[i] = -1e9;
		for(int i=1;i<=1000000;i++) ex[pos[i].fi][pos[i].sc] = 0;
		for(int i=1;i<=m;i++) ex[pos[i].fi][pos[i].sc] = 1;
		dp[n] = 0;
		if(!pr[n]) dp[n] = 1;
		int x = pos[n].fi, y = pos[n].sc;
		for(int i=x;i<=3005;i++){
			for(int j=0;j<3005;j++){
				if(!ex[i][j]) continue;
				if(ex[i+1][j]){dp[val[i+1][j]] = max(dp[val[i+1][j]],dp[val[i][j]]+!pr[val[i+1][j]]);}
				if(j&&ex[i+1][j-1]){dp[val[i+1][j-1]] = max(dp[val[i+1][j-1]],dp[val[i][j]]+!pr[val[i+1][j-1]]);}
				if(ex[i+1][j+1]){dp[val[i+1][j+1]] = max(dp[val[i+1][j+1]],dp[val[i][j]]+!pr[val[i+1][j+1]]);}
			}
		}
		int ans1 = 0, ans2 = 0;
		for(int i=1;i<=m;i++){
			if(dp[i] > ans1){
				ans1 = dp[i]; ans2 = i;
			}
			else if(dp[i] == ans1 && !pr[i]){ ans2 = max(ans2,i); }
		}
		if(ans1 == 0) puts("0 0");
		else cout << ans1 << " " << ans2 << endl;
	}
}



Measured memory_bytes: 28384
#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define FOR(i,n) for (int i = 0; i < n; i++)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

string s;

char mex (string &s) {
	bitset<255> bs;
	
	for (char c : s)
		bs[c] = 1;
	
	for (char c = 'a'; c <= 'z'; c++)
		if (!bs[c])
			return c;

	return 'a';
}

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

 	if (s.size() < 26) {
 		cout << s << mex(s) << endl;
 	} else {
 		string a = s;

 		if (!next_permutation(a.begin(), a.end())) {
 			cout << -1 << endl;
 		} else {
 			int i = 0;
 			while (s[i] == a[i]) {
 				cout << s[i];
 				i++;
 			}
 			cout << a[i] << 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 m = sc.nextInt();

    int a[] = new int[m];
    int b[] = new int[m];
    int c[] = new int[n];

    for (int i =0; i < m; i++) {
      a[i] = sc.nextInt();
      b[i] = sc.nextInt();
    }

    for (int i =0; i < m; i++) {
      for (int j =0; j < n; j++) {
        if(a[i] == j+1) c[j]++;
        if(b[i] == j+1) c[j]++;
      }
    }

    for (int i =0; i < n; i++) {
      System.out.println(c[i]);
    }

  }  
}


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

//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;

const int MAX = 1 << 17;

int a[MAX], b[MAX], c[MAX];

int main()
{
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	FOR(i, 0, n)
		cin >> a[i];
	FOR(i, 0, n)
		cin >> b[i];
	FOR(i, 0, n)
		cin >> c[i];
	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);
	int ptr1 = 0, ptr2 = 0;
	LL ans = 0;
	FOR(i, 0, n)
	{
		while(ptr1 < n && a[ptr1] < b[i])
			ptr1++;
		while(ptr2 < n && c[ptr2] <= b[i])
			ptr2++;
		ans += (LL)ptr1 * (n - ptr2);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<cstring>
short dp[305][305][305];
char in[310];
void upd(short &x, short y) {
	if (x < y) x = y;
}
int main() {
	int n, k;
	scanf("%s%d", in+1, &k);
	n = strlen(in+1);
	for (int i = 1; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][i][j] = 1;
	for (int d = 1; d <= n; d++) {
		for (int i = 1; i + d <= n; i++) {
			int j = i + d;
			for (int t = 0; t <= k; t++) {
				upd(dp[i][j][t], dp[i + 1][j][t]);
				upd(dp[i][j][t], dp[i][j - 1][t]);
			}
			if (in[i] == in[j]) {
				for (int t = 0; t <= k; t++) upd(dp[i][j][t], dp[i + 1][j - 1][t] + 2);
			}
			else {
				for (int t = 1; t <= k; t++) upd(dp[i][j][t], dp[i + 1][j - 1][t-1] + 2);
			}
		}
	}
	printf("%d\n", dp[1][n][k]);
	return 0;
}

Measured memory_bytes: 55296
#include<stdio.h>
int max2(int a, int b){return a<b?b:a;}
int x;
int ans, i, j;
int main(){
  scanf("%d", &x);
  if(x==1){
    printf("1\n");
    return 0;
  }
  for(i=2; i<x; i++){
    for(j=i*i; j<=x; j*=i){
      ans=max2(ans, j);
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 128
#include<stdio.h>

int main(){
  int h,w;
  scanf("%d%d",&h,&w);
  char s[w];
  
  for(int i=0;i<w+2;i++) printf("#");
  printf("\n");
  for(int i=0;i<h;i++){
    printf("#");
    scanf("%s",s);
    for(int j=0;j<w;j++)
      printf("%c",s[j]);
    printf("#\n");
  }
  for(int i=0;i<w+2;i++) printf("#");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i = 0; i < N; i++) cin >> a[i];
    long long ans = 0;
    for(int i = 0; i < N; i++) ans += a[i] - 1;
    cout << ans << endl;
}

Measured memory_bytes: 256
// AOJ 1622 Go around the Labyrinth
// 2018.2.13 bal4u

#include <stdio.h>
#include <string.h>

typedef struct { char r, c, d, k; } STACK;
STACK sk[3000]; int top;
char map[53][53];
char mk[53][53];
int mv[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int check(int h, int w)
{
	int i, r, c, d, k, nr, nc;

	memset(mk, 0, sizeof(mk));
	sk[0].r = 1, sk[0].c = 1, sk[0].d = 1, sk[0].k = 1, top = 1;
	while (top) {
		r = sk[--top].r, c = sk[top].c, d = sk[top].d, k = sk[top].k;

		if (mk[r][c]) continue;
		mk[r][c] = 1;

		if      ((k & 1) && r == h && c == 1) k |= 2;
		else if ((k & 2) && r == h && c == w) k |= 4;
		else if ((k & 4) && r == 1 && c == w) k |= 8;
		else if ((k & 8) && r == 1 && c == 2) return 1;

		d += 2; if (d >= 4) d -= 4;
		for (i = 0; i < 4; i++) {
			if (++d == 4) d = 0; 
			nr = r + mv[d][0], nc = c + mv[d][1];
			if (map[nr][nc] && !mk[nr][nc]) {
				sk[top].r = nr, sk[top].c = nc, sk[top].d = d, sk[top++].k = k;
			}
		}
	}
	return 0;
}

int main()
{
	int h, w, r, c;
	char buf[10], *p;

	while (fgets(buf, 10, stdin) && *buf != '0') {
		sscanf(buf, "%d%d", &h, &w);
		memset(map, 0, sizeof(map));
		for (r = 1; r <= h; r++) {
			fgets(p=map[r]+1, 52, stdin);
			c = w; while (c--) *p = (*p == '.'), p++; *p = 0;
		}
		puts(check(h, w)? "YES": "NO");
	}
	return 0;
}



Measured memory_bytes: 1980
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
#define lo long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
long long n,k,d,ans;
long long a[1002];
vector<long long>v,V;
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
for(long long i=0;i<n;i++)
{
	cin>>a[i];
}
for(long long i=0;i<n;i++)
{
	d=a[i];
	v.push_back(d);
	for(long long j=i+1;j<n;j++)
	{
		d=(d+a[j]);
		v.push_back(d);
//		cout<<d<<" ";
	}
}
for(long long i=40;i>=0;i--)
{
	for(long long j=0;j<v.size();j++)
	{
		if((v[j]&(1LL<<i))==0LL)continue;
		V.push_back(v[j]);
	}
	if(V.size()>=k)
	{
		v=V;
		ans|=(1LL<<i);
//		cout<<ans<<endl;
	}
	V.clear();
}
cout<<ans<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
               *       * *       *
               *        *        *
                *               *
                 *             *
                  *           *
                   *         *
                    *       *
                     *     *
                      *   *
                       * *
                        *



*/





Measured memory_bytes: 6256
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto x:v)cerr<<x<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define EPS 1e-9
typedef long long ll;

signed main(){
  string S;
  cin >> S;
  FOR(i,0,3){
    if(S[i] == '1')S[i] = '9';
    else if(S[i] == '9')S[i] = '1';
  }
  cout << S << endl;
}

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

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i], B[i] = A[i] - i;

    // メディアンを
    sort(B.begin(), B.end());
    long long x = B[N/2];

    // 答えを求める
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        res += max(x - B[i], -x + B[i]); // |A| = max(A, -A)
    }
    cout << res << endl;
}


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

const ll mx = 1e7 + 9;
ll par[mx];
ll p_u, p_v;

ll find_parent(ll x) {
    if(x == par[x]) return x;

    return par[x] = find_parent(par[x]);
}

void join(ll v, ll u) {
    p_u = find_parent(u);
    p_v = find_parent(v);

    if(p_v == p_u) return;
    par[p_u] = p_v;
}


int main() {
    ll n, m;  cin >> n >> m;
    for(ll i = 1; i <= n; i++) {
        par[i] = i;
    }


    while(m--) {
        ll u, v; cin >> u >> v;
        join(u, v);
    }

    map<ll, ll>mm;

    for(ll i = 1; i <= n; i++) {
        ll k = find_parent(i);
        mm[k]++;
    }
    ll ans = 0;
    for(auto i : mm) {
        ans = max(ans, i.second);
    }
    cout << ans << endl;
    return 0;

}



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

int day(int y, int m, int d)
{
	int day = 0;
	day += (y - 1) * 195 + (y - 1) / 3 * 5;
	day += (y % 3 == 0) ? (m - 1) * 20 : (m - 1) * 20 - (m - 1) / 2;
	day += d;
	return day;
}

int main()
{
	int n, Y, M, D;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> Y >> M >> D;
		cout << day(1000, 1, 1) - day(Y, M, D) << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};

const int M_N=600000;

struct BIT{
    //1-indexed
    int n;
    vector<int> bit;
    void init(int k){
        n = k;
        bit.assign(M_N,0);
    }
    //iまでの総和を返す
    LL sum(int i){
        LL s=0;
        while(i>0){
            s+=bit[i];
            i=i&(i-1);
        }
        return s;
    }
    //iにx加算する
    void add(int i,LL x){
        while(i<=n){
            bit[i]+=x;
            i+=i&-i;
        }
    }
};


int main(){
    int n;cin >> n;
    string s;cin >> s;
    BIT bit[26];
    for (int i = 0; i < 26; i++) {
        bit[i].init(n);
    }
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < 26; j++) {
            if(s[i] - 'a' == j) bit[j].add(i+1, 1);
        }
    }
    int q;cin >> q;
    while(q--){
        int t;cin >> t;
        if(t==1){
            int l;
            char c;cin >> l >> c;
            int r = c - 'a';
            int a = bit[r].sum(l) - bit[r].sum(l-1);
            if(a==0) bit[r].add(l,1);
            for (int i = 0; i < 26; i++) {
                if(i==r) continue;
                a = bit[i].sum(l) - bit[i].sum(l-1);
                if(a==1) bit[i].add(l,-1);
            }
        }
        else{
            int l,r;cin >> l >> r;
            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if(bit[i].sum(r) - bit[i].sum(l-1) >= 1) ans++;
            }
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 63876
X, Y = [int(x) for x in input().split()]
prize = 0

prize_list = {1:300000, 2:200000, 3:100000}

if X > 0 and X < 4:
    prize += prize_list[X]

if Y > 0 and Y < 4:
    prize += prize_list[Y]

if prize == 600000:
    prize = 1000000

print(prize)

Measured memory_bytes: 3064
//#include <bits/stdc++.h>
#include <iostream>
#include <cmath>

using namespace std;

#define rep(i , n) for(int i=0 ; i<n ; i++)
#define rep1(i , n) for(int i=1 ; i<=n ; i++)

typedef long long int ll;

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

	int n,d;
	cin >> n >> d;
	int mat[11][11];

	rep(i , n)
	{
		rep(j , d)
			cin >> mat[i][j];
	}

	int count = 0;
	rep(i , n)
	{
		for(int j=i+1 ; j<n ; j++)
		{
			int temp = 0;
			for(int k=0 ; k<d ; k++)
				temp += pow(abs(mat[i][k]-mat[j][k]) , 2);
			
			int temp1 = sqrt((double)temp);
			if(temp1 == sqrt(temp))
				count++;
		}	
	}

	cout << count;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 5007
#define inf 9223372036854775806
using namespace std;
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  return f ? -x : x;
}

ll ans = -inf;

int n, k, c[N], nxt[N];

inline void calc1(int x) {
  ll sum = 0;
  int tar = x, t = 0;
  while (nxt[x] != tar) {
    if (t >= k) break;
    ++t; sum += c[nxt[x]];
    ans = max(ans, sum);
    x = nxt[x];
  }
}

inline void calc2(int x) {
  ll sum = 0;
  int tar = x, t = 0;
  while (nxt[x] != tar) {
    if (t >= k) return;
    ++t; sum += c[nxt[x]];
    x = nxt[x];
  }
  if (t >= k) return;
  ++t; sum += c[nxt[x]];
  x = nxt[x];
  if (sum <= 0) return;
  sum = sum * (k / t);
  ans = max(ans, sum);
  t = (k / t) * t;
  while (nxt[x] != tar) {
    if (t >= k) break;
    ++t; sum += c[nxt[x]];
    ans = max(ans, sum);
    x = nxt[x];
  }
}

inline void calc3(int x) {
  ll sum = 0;
  int tar = x, t = 0;
  while (nxt[x] != tar) {
    if (t >= k) return;
    ++t; sum += c[nxt[x]];
    x = nxt[x];
  }
  if (t >= k) return;
  ++t; sum += c[nxt[x]];
  x = nxt[x];
  if (sum <= 0) return;
  sum = sum * ((k / t) - 1);
  ans = max(ans, sum);
  t = ((k / t) - 1) * t;
  while (nxt[x] != tar) {
    if (t >= k) break;
    ++t; sum += c[nxt[x]];
    ans = max(ans, sum);
    x = nxt[x];
  }
}

int main() {
  n = rd();
  k = rd();
  for (int i = 1; i <= n; ++i) nxt[i] = rd();
  bool f = 0;
  int mx = -2147483640;
  for (int i = 1; i <= n; ++i) {
    c[i] = rd();
    if (c[i] > 0) f = 1;
    mx = max(mx, c[i]);
  }
  if (!f) {printf("%d\n", mx); return 0;}
  for (int i = 1; i <= n; ++i) calc1(i);
  for (int i = 1; i <= n; ++i) calc2(i);
  for (int i = 1; i <= n; ++i) calc3(i);
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 3756
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args) {
        string s = Console.ReadLine();
        Console.WriteLine(solve(s, s.Length));
    }
    static int solve(string s, int n) {
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < n; i ++) {
          	if(s[i] != '1') {
              if (i % 2 == 0) count1 ++;
              else count2 ++;
            } else {
              if (i % 2 == 0) count2 ++;
              else count1 ++;
            }
        }
        return Math.Min(count1,count2);
    }
}

Measured memory_bytes: 11232
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MOD = (int)1e9 + 7;
const int MAXN = 234567;
int sz[MAXN];
LL invpw2[MAXN];
vector<int> G[MAXN];

LL qpow(LL n, LL p) {
    LL base = n, ans = 1;
    while (p) {
        if (p % 2) ans = (ans * base) % MOD;
        p >>= 1;
        base = (base * base) % MOD;
    }
    return ans;
}

LL mul(LL a, LL b) {
    return (a * b) % MOD;
}

LL add(LL a, LL b) {
    LL ans = (a + b);
    if (ans >= MOD) ans -= MOD;
    return ans;
}

LL sub(LL a, LL b) {
    return (a - b + MOD) % MOD;
}

int dfs(int cur, int par, LL &ans, int N) {
    int sz = 1;
    LL cur_ans = 0;
    for (int i : G[cur]) {
        if (i == par) continue;
        int tmp = dfs(i, cur, ans, N);
        LL tmp_ans = mul(sub(1, invpw2[tmp]), invpw2[N - tmp - 1]);
        sz += tmp;
        cur_ans = add(cur_ans, tmp_ans);
    }
    LL tmp_ans = mul(sub(1, invpw2[N - sz]), invpw2[sz - 1]);
    cur_ans = add(cur_ans, tmp_ans);
    cur_ans = add(cur_ans, invpw2[N - 1]);
    cur_ans = sub(1, cur_ans);
    cur_ans = mul(cur_ans, invpw2[1]);
    ans = add(ans, cur_ans);
    return sz;
}

int main() {
    int N;
    scanf("%d", &N);
    invpw2[0] = 1;
    invpw2[1] = qpow(2, MOD - 2);
    for (int i = 2; i <= N; i++)
        invpw2[i] = (invpw2[i - 1] * invpw2[1]) % MOD;
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    LL ans = 0;
    dfs(1, 1, ans, N);
    printf("%lld\n", ans);
    return 0;
}


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

int main() {
  int N, NN, a=0;
  cin >> N;
  NN = N;
  
  while (NN != 0) {
    int b;
    b=NN-NN/10*10;
    a += b;
    NN = NN/10;
  }
  
  int c;
  c = N%a;
  
  if (c==0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3628
def p_c():
    from itertools import permutations
    from math import sqrt
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    ans = []
    for per in permutations(list(range(n))):
        x, y = xy[per[0]]
        dist = 0
        for i in per[1:]:
            x2, y2 = xy[i]
            dist += sqrt((x2 - x) ** 2 + (y2 - y) ** 2)
            x, y = x2, y2
        ans.append(dist)
    print(sum(ans) / len(ans))
    
p_c()

Measured memory_bytes: 42092
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long h;
    long n;
    cin >> h >> n;
    vector<long> a(n);
    long long sum;
    sum = 0;
    long i;
    for( i=0; i<n; i++){
        cin >> a.at(i);
    }
    for( i=0; i<n; i++){
        sum = sum + a.at(i);
    }
    if( h<=sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}




Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int N=200010,Mod=998244353;
const double pi=acos(-1.0);
typedef long long int ll;
typedef pair<int,int> pii;
int n,a[N];
multiset<int> last;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    auto it=last.lower_bound(a[i]);
    if(it==last.begin()) last.insert(a[i]);
    else
    {
      it--;
      last.erase(it);
      last.insert(a[i]);
    }
  }
  cout<<last.size()<<endl;
  return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define sz(x) ((int) x.size())
#define rd(type, ...) type __VA_ARGS__; sc(__VA_ARGS__)
#define rdv(type, v, n) vector<type> v(n); rep(__ii, 0, n) cin >> v[__ii]
#define rdm(type, v, h, w) vector<vector<type>>(h, vector<type>(w)) v; rep(__ii, 0, h) rep(__jj, 0, w) cin >> v[__ii][__jj]
typedef long long ll;
void solve();
signed main() {ios::sync_with_stdio(false); cin.tie(0);
  cout << fixed; cout.precision(12); solve(); return 0;}
template<typename T> void prv(vector<T> v) {rep(__ii, 0, sz(v)) {if (__ii) cout << ' '; cout << v[__ii];} cout << '\n';} 
template<typename T> void prm(vector<vector<T>> v) {rep(__ii, 0, sz(v)) {rep(__jj, 0, v[__ii].size()) {if (__jj) cout << ' '; cout << v[__ii][__jj];} cout << '\n';}}
template<typename T> void sc(T& x) {cin >> x;}
template<typename Head, typename... Tail> void sc(Head& head, Tail&... tail) {cin >> head; sc(tail...);}
template<typename T> void pr(const T& x) {cout << x << '\n';}
template<typename Head, typename... Tail> void pr(const Head& head, const Tail&... tail) {cout << head << ' '; pr(tail...);}
template<typename... T> void err(const T&... cod) {pr(cod...); exit(0);}

const int N = 2e5 + 10;

int a[N], b[N];

void solve() {
  rd(int, n);
  rep(i, 1, n + 1) cin >> a[i];
  per(i, n, n / 2 + 1) b[i] = a[i];
  per(i, n / 2, 1) {
    int sum = 0;
    for (int j = i + i; j <= n; j += i) sum += b[j];
    sum %= 2;
    if (a[i]) b[i] = (sum ? 0 : 1);
    else b[i] = (sum ? 1 : 0);
  }
  vector<int> ans;
  rep(i, 1, n + 1) if (b[i]) ans.pb(i);
  pr(sz(ans));
  prv(ans);
}

Measured memory_bytes: 3704
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef complex<ld> Point;
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int max_n;
const int mn = 100000;
struct edge {
	int to, cap, cost, rev;
};
vector<edge> G[mn];
int par[mn];
int dist[mn];
void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back({ to,cap,cost,(int)G[to].size() });
	G[to].push_back({ from,0,-cost,(int)G[from].size() - 1 });
	max_n = max({ max_n, from + 1, to + 1 });
}
int minimum_road(int s, int t) {
	fill(par, par + max_n, -1);
	fill(dist, dist + max_n, mod);
	dist[s] = 0;
	priority_queue<P, vector<P>, greater<P>> q; q.push({ 0,s });
	while (!q.empty()) {
		P p = q.top(); q.pop();
		int id = p.second;
		if (id == t)continue;
		rep(j, G[id].size()) {
			if (G[id][j].cap > 0) {
				int to = G[id][j].to;
				int nd = p.first + G[id][j].cost;
				if (nd < dist[to]) {
					dist[to] = nd;
					par[to] = id;
					q.push({ dist[to],to });
				}
			}
		}
	}
	int cur = t;
	while (cur != s) {
		int p = par[cur];
		if (p < 0)return -1;
		rep(j, G[p].size()) {
			if (G[p][j].cap > 0 && G[p][j].to == cur && dist[p] + G[p][j].cost == dist[cur]) {
				G[p][j].cap--;
				G[cur][G[p][j].rev].cap++;
				break;
			}
		}
		cur = p;
	}
	return dist[t];
}
int minimum_cost_flow(int s, int t) {
	int ret = 0;
	while(true) {
		int z = minimum_road(s, t);
		if (z < 0)break;
		ret += z;
	}
	return ret;
}

int x[1000], y[1000];
void solve() {
	int n; cin >> n;
	int ans = 0;
	vector<int> v;
	rep(i, n) {
		cin >> x[i] >> y[i];
		ans += x[i] + y[i];
		v.push_back(x[i]);
		v.push_back(y[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	map<int, int> mp;
	rep(i, v.size()) {
		mp[v[i]] = i;
	}
	int s = 4 * n; int t = s + 1;
	rep(i, v.size()) {
		add_edge(s, i, 1, 0);
	}
	rep(i, n) {
		int idx = mp[x[i]];
		int idy = mp[y[i]];
		int id = i + v.size();
		add_edge(id, t, 1, 0);
		add_edge(s, id, 1, x[i] + y[i]);
		add_edge(idx, id, 1, x[i]);
		add_edge(idy, id, 1, y[i]);
	}
	ans -= minimum_cost_flow(s, t);
	cout << ans << endl;
}
int main() {
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 5976
#include<cstdio>
#include<iostream>
using namespace std;
const int MR=100010;


char a[MR];
char ans[MR];
bool check(int a1,int a2,int n){
	a[0]='S'+a1*('W'-'S');a[1]='S'+a2*('W'-'S');
	for(int i=1;i<=n;i++){
		if((a[i]=='S' && ans[i]=='o')||(a[i]=='W' && ans[i]=='x')) a[i+1]=a[i-1];
		if((a[i]=='S' && ans[i]=='x')||(a[i]=='W' && ans[i]=='o')) a[i+1]='S'+'W'-a[i-1];
	}
	if(a[n]==a[0] && a[n+1]==a[1]){
		a[n]=0;
		return true;
	}
	else return false;
	
}

int main(){
	int n;
	scanf("%d",&n);
	cin.getline(ans,n+1);
	cin.getline(ans,n+1);
	ans[n]=ans[0];
	int a1,a2;
	bool ok=false;
	for(a1=0;a1<2;a1++){
		for(a2=0;a2<2;a2++){
			if(check(a1,a2,n)){
				ok=true;
				break;
			}
		}
		if(ok)break;
	}
	if(ok)printf("%s\n",a);
	else printf("-1\n");
	return 0;
}

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

#define vec(v) vector<int>(v)
#define be(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define mapci(mp) map<char*,int>(mp)
#define mapcc(mp) map<char*,char*>(mp)
typedef long long ll;
using namespace std;

int main() {
   int n,m,a,k,count[10000000],ans=0;
   cin>>n>>m;
   for(int i=0; i<n;i++){
       count[i]=0;
   }
   for(int i=0;i<n;i++){
       cin>>k;
       for(int j=0;j<k;j++){
           cin>>a;
           count[a-1]++;
       }
   }
   for(int i=0;i<m;i++){
       if(count[i]==n){
           ans++;
       }
   }
   cout<<ans<<endl;
    return 0;
}


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

using namespace std;

int n,a,b,c,d;
char s[200005];
int sign = 0;

int main()
{
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    scanf("%s",s);
    int n = strlen(s);
    if(s[c - 1] == '#' || s[d - 1] == '#')
    {
        printf("No\n");
        return 0;
    }
    if(c < d)
    {
        for(int i = a - 1;i < d - 1;i++)
        {
            if(s[i + 1] == '#' && s[i] == '#')
            {
                printf("No\n");
                return 0;
            }
        }
        printf("Yes\n");
        return 0;
    }
    else
    {
        for(int i = a - 1;i < c - 1;i++)
        {
            if(s[i + 1] == '#' && s[i] == '#')
            {
                printf("No\n");
                return 0;
            }
        }
        for(int i = b - 1;i <= d - 1;i++)
        {
            if(s[i + 1] == '.' && s[i] == '.' && s[i - 1] == '.')
            {
                sign++;
            }
        }
    }
    if(sign > 0)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 384
import re
import copy
n = int(input())
str = input()
Origin = list(str.split())

# bubble sort
A = copy.deepcopy(Origin)   #list はMutableなのでおおもとからコピーすると元も変わる
B = []*n

for i in range(n):
    B.append(int(re.sub("\\D","",A[i])))
flag = 1
i = 0
while flag:
    flag = 0
    for j in range(n-1,i,-1):
        if B[j] < B[j-1]:
            buf1 = B[j-1]
            buf2 = A[j-1]
            B[j-1] = B[j]
            A[j-1] = A[j]
            B[j] = buf1
            A[j] = buf2
            flag = 1
    i += 1

# selection sort
C = copy.deepcopy(Origin)
D = []*n
for i in range(n):
    D.append(int(re.sub("\\D","",C[i])))
for k in range(n):
    min_k = k
    for l in range(k,n):
        if D[l] < D[min_k]:
            min_k = l
    if min_k != k:#未ソートの部分の一番左がMinjの場合には何もしない
        buf1 = D[k]
        buf2 = C[k]
        D[k] = D[min_k]
        C[k] = C[min_k]
        D[min_k] = buf1
        C[min_k] = buf2

for i in range(n):
    if i != n-1:print(A[i],"",end="")
    else: print(A[i])
print("Stable")
for i in range(n):
    if i != n-1:print(C[i],"",end="")
    else: print(C[i])

if A != C: print("Not stable")
else: print("Stable")


Measured memory_bytes: 6596
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
#define endl '\n'
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define sz(v) (int)v.size() 
#define UB upper_bound
#define LB lower_bound
#define BP(x) __builtin_popcountll(x)
#define PQS priority_queue <int, vector<int>, greater<int> > 
#define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r) {
  uniform_int_distribution<int> uid(l, r);
  return uid(rng);
}

const int INF = 1e18 + 0;
const int mod = 1e9 + 7;
//const int mod = 998244353;

void solve() {
  string s; cin >> s;
  if(s.back() == 's') {
    s += 'e';
  }
  s += 's';
  cout << s << '\n';
}

/*
  * overflow, array bounds
  * do smth instead of nothing and stay organized
*/
signed main() {   
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  #ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
  #endif
   int t = 1; // cin >> t;
   for(int i = 1; i <= t; i++) {
   //  cout << "Case #" << i << ": ";
     solve();
  }
}    

/*

*/

Measured memory_bytes: 3656
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int b[] = new int[n+1];
    b[0] = 10000000;
    b[n] = 10000000;
    int answer=0;
    for(int i=1;i<n;i++){
      b[i] = sc.nextInt();
    }
    for(int i=0;i<n;i++){
      answer = answer + Math.min(b[i],b[i+1]);
    }
    System.out.println(answer);
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
  int N; cin >> N;
  vector<ll> x(N), y(N);
  rep(i, N) cin >> x[i] >> y[i];
  vector<ll> f1(N), f2(N);
  ll mx1 = -INF, mx2 = -INF, mn1 = INF, mn2 = INF;
  rep(i, N) {
    f1[i] = x[i] - y[i];
    f2[i] = x[i] + y[i];
    chmax(mx1, f1[i]);
    chmax(mx2, f2[i]);
    chmin(mn1, f1[i]);
    chmin(mn2, f2[i]);
  }
  cout << max(mx1 - mn1 , mx2 - mn2) << endl;
}


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

int main() {
  string s;
  cin >> s;
  for (int i=0; i<s.size(); i++) {
    if (s.at(i) == ',')
      cout << ' ';
    else
      cout << s.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
dic = {}
for i in range(input()):
    dic[i+1] = []
for i in range(input()):
    x, y = map(int, raw_input().split())
    dic[y].append(x)

del dic[2]
ans  = []
while True:
    lis = sorted(dic.items(), key=lambda x: len(x[1]))
    k = lis[0][0]
    del dic[k]
    ans.append(k)
    if not dic: break
    for v in dic.values():
        if k in v:
            v.remove(k)

for v in ans:
    print v
else:
    print 2

Measured memory_bytes: 4240
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <numeric>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;

const int INF = 1 << 30;
const double EPS = 1e-10;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main()
{
  int N, K;
  while (cin >> N >> K) {
    vector<int> bunny(N);
    for (int i = 0; i < K; ++i) {
      int m;
      cin >> m;
      for (int j = 0; j < m; ++j) {
        int b;
        cin >> b;
        bunny[b-1] = i;
      }
    }

    int R;
    cin >> R;
    vector<int> ans(N, 0);
    for (int i = 0; i < R; ++i) {
      int p, q;
      cin >> p >> q;
      --p;
      --q;
      if (bunny[p] == bunny[q]) {
        ans[p] = ans[q] = 1;
      }
    }

    cout << count(ans.begin(), ans.end(), 1) << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
s =input()
last = len(s)-1
count=0
if(len(s)%2==0):
    for i in range(int(len(s)/2)):
        if(s[i]!=s[last]):
            count+=1
        last -= 1
elif(len(s)%2!=0):
    for i in range(int(len(s)//2)):
        if(s[i]!=s[last]):
            count+=1
        last -= 1

print(count)

Measured memory_bytes: 3064
n,m=map(int,input().split())
d=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 or b==1 or a==n or b==n:
    d[a-1].append(b)
    d[b-1].append(a)
for i in d[n-1]:
  if 1 in d[i-1]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Measured memory_bytes: 40724