akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
vector<int> v[100010];
int n;
int d[100010][2];
vector<int> tp;
bool visit[100010];
ll md=1e9+7;
void dfs(int x)
{
	visit[x]=1;
	for (int i=0;i<v[x].size();i++)
	{
		int xi=v[x][i];
		if (!visit[xi]) dfs(xi);
	}
	tp.push_back(x);
}
int main()
{
	cin >>n;
	for (int i=0;i<n-1;i++)
	{
		int x,y;
		cin >>x>>y;
		x--,y--;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(0);
	fill(visit,visit+n,0);
	for (int i=0;i<n;i++)
	{
		int x=tp[i];
		visit[x]=1;
		ll xt=1,yt=1;
		for (int j=0;j<v[x].size();j++)
		{
			int xi=v[x][j];
			if (visit[xi])
			{
				xt=(xt*((d[xi][0]+d[xi][1])%md))%md;
				yt=(yt*d[xi][0])%md;
			}
		} 
		d[x][0]=xt,d[x][1]=yt;
	}
	cout <<(d[0][0]+d[0][1])%md;
	return 0;
}

Measured memory_bytes: 9848
#include <iostream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
using namespace std;


int main(){
  int N;
  cin >> N;
  int C [9][9];
  for (int i = 1; i < 10; i++){
    for (int j = 1; j < 10; j++){
      int count = 0;
      for (int n = 1; n <= N; n++){
        int j2 = n % 10;
        int tempn = n;
        while(!(tempn < 10)){
          tempn = tempn/10;
        }
        int i2 = tempn;
        if (i2 == i && j2 == j ) count++;
      }
      C[i-1][j-1] = count;
    }
  }

  int ans = 0;
  for (int i = 0; i < 9; i++){
    for (int j = 0; j < 9; j++){
      ans = ans + C[i][j] * C[j][i];
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    sort(a,a+n);
    int l=1,r=n-1,tl=0,tr=0;
    ll ans=0;
    int flag=1;
    while(l<=r)
    {
        long long k1=abs(a[tl]-a[l]),k2=abs(a[tl]-a[r]),k3=abs(a[tr]-a[l]),k4=abs(a[tr]-a[r]);
        if(k1>=k2&&k1>=k3&&k1>=k4)
        {
            ans+=k1;
            tl=l;l++;
        }
        else if(k2>=k1&&k2>=k3&&k2>=k4)
        {
            ans+=k2;
            tl=r;r--;
        }
        else if(k3>=k1&&k3>=k2&&k3>=k4)
        {
            ans+=k3;
            tr=l;l++;
        }
        else if(k4>=k1&&k4>=k2&&k4>=k3)
        {
            ans+=k4;
            tr=r;r--;
        }
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 1024
#pragma warning( disable : 6031)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
int minimum(int a, int b) { return a < b ? a : b; }
int maximum(int a, int b) { return a > b ? a : b; }
const long long mod = 1000000007;
//const long long mod = 998244353;
using std::vector;
using std::pair;
using std::string;
using std::map;
using std::abs;
int main() {
	int A, B, C, K;
	scanf("%d %d %d %d", &A, &B, &C, &K);
	int res = 0;
	if (K < A) {
		res += K;
		K = 0;
	}
	else {
		res += A;
		K -= A;
	}
	if (K < B) {
		K = 0;
	}
	else {
		K -= B;
	}
	if (K < C) {
		res -= K;
		K = 0;
	}
	else {
		res -= C;
		K -= C;
	}
	printf("%d", res);
	return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n;
    string s;
    cin >> n >> s;
    REP(i,s.size()){
        s[i]+=n;
        if(s[i]>90) s[i]=s[i]%90+64;
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3656
N = int(input())
W = list(map(int, input().split()))
minDif = 10**8
accumW = [0]
for i in range(N):
    accumW.append(accumW[i]+W[i])
for i in range(1, N):
    minDif = min(minDif, abs(accumW[N] - 2*accumW[i]))
print(minDif)


Measured memory_bytes: 3060
/*
 
                              Jai Shree Krishna !!
                                 Radhe Radhe !!
                                 
             उद्यमेन हि सिद्ध्यन्ति कार्याणि न मनोरथैः। नहि सुप्तस्य सिंहस्य मुखे प्रविशन्ति मृगाः।।
             
*/
   
   
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long long ll;
#define loop(i,n)  for(int i=0;i<n;i++)
#define ford(i,a,b) for(int i=b;i>=a;i--)
#define read(a) int a; cin >>a;
#define readarr(a,n) int a[n] ; for(int i=0;i<n;i++) cin >> a[i];
#define readmat(a,n,m) int a[n][m]; for(int i=0;i<n;i++) for(j=0;j<m;j++) cin >> a[i][j];
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define pi pair<int,int>
#define vii vector<vector<int>>
#define sti set<int>
#define vpi vector<pair<int,int>>
#define print(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define printmat(a,n,m) for(int i=0;i<n;i++) {for(j=0;j<m;j++) cout<<a[i][j]<<" "; cout<<endl;}
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define endl "\n"
#define mp make_pair
const ll inf = 1e18;
const ll mod = 1e9 + 7;
 

signed main()
{
 
    fast;
     string s,t;
     cin >> s>>t;
     if(s.length()==t.length()-1){
        if(t.substr(0,s.length())==s)
        cout<<"Yes"<<endl;
        else
        cout<<"No";
     }
     else
     cout<<"No";
    return 0;
}
 
/* Pooja Yadav */

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

// 入力
long long N;

// cur: 現在の値、use: 7, 5, 3 のうちどれを使ったか, counter: 答え
void func(long long cur, int use, long long &counter){
    if (cur > N) return; // ベースケース
    if (use == 0b111) ++counter; // 答えを増やす

    // 7 を付け加える
    func(cur * 10 + 7, use | 0b001, counter);

    // 5 を付け加える
    func(cur * 10 + 5, use | 0b010, counter);

    // 3 を付け加える
    func(cur * 10 + 3, use | 0b100, counter);
}

int main() {
    cin >> N;
    long long res = 0;
    func(0, 0, res);
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) {
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int main() {
  string S; cin>>S;
  bool ans = S[0]==S[1] || S[1]==S[2] || S[2]==S[3];
  TorF(ans, "Bad", "Good");
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int w,h,x,y,r;
    cin >> w >> h >> x >> y >> r;
    if(x - r < 0 || x + r > w || y - r < 0 || y + r > h)
    {
        cout << "No\n";
    }
    else
    {
        cout << "Yes\n";
    }
    
    return 0;
}


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

int main() {
	int a, b;
	cin >> a >> b;
	if (a < 9 && b < 9) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}
int i,n;

int main()
{
  cin>>n;
  i=2;
  cout<<n*i/__gcd(n,i);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S, T;
  cin >> S >> T;

  //cout << T.substr(0, S.length()) << endl;
  
  if (T.substr(0, S.length()) == S) {
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3572
from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)


Measured memory_bytes: 3736
N = int(input())
h_list = list(map(int, input().split()))

dp = [0] * (N)
for i in range(1, N):
    h1 = abs(h_list[i] - h_list[i-1])
    h2 = abs(h_list[i] - h_list[i-2]) if i >= 2 else 10**9
    dp[i] = min(dp[i-1] + h1, dp[i-2] + h2)

print(dp[-1])

Measured memory_bytes: 13976
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s: usize
    }
    let a = s / 100;
    let b = s % 100;
    let fa = 1 <= a && a <= 12;
    let fb = 1 <= b && b <= 12;
    if fa && fb {
        println!("AMBIGUOUS");
    } else if fa {
        println!("MMYY");
    } else if fb {
        println!("YYMM");
    } else {
        println!("NA");
    }
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

string s;

bool sub() {
  for (int i = 0; i < 3; ++i) {
    if (s[i] == s[i + 1]) return false;
  }
  return true;
}

int main() {
  cin >> s;
  cout << (sub() ? "Good" : "Bad") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;i+=2)
using namespace std;

vector<int> divisor(int n){
  vector<int> res;
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      res.push_back(i);
      if(i!=n/i)res.push_back(n/i);
    }
  }
  return res;
}

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

  int ans=0;
  rep(i,n){
    vector<int> div=divisor(i);
    if(div.size()==8)ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

bool check(string s) {
	bool ret = true;
	rep(i, sz(s)) {
		if (s[i] != 'A'&&s[i] != 'C'&&s[i] != 'G'&&s[i] != 'T')ret = false;
	}
	return ret;
}

int main() {
	string s; cin >> s;
	int n = sz(s);

	int ans = 0;
	rep(i, n) {
		FOR(j, i, n) {
			if (check(s.substr(i, j - i + 1)))ans = max(ans, j - i + 1);
			//dump(s.substr(i, j - i + 1));
		}
	}
	Cout(ans);
}

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

int main(){
    int n, k; cin >> n >> k;
    vector<long long> dist(n);
    for(int i = 0; i < n; i++) cin >> dist.at(i);
    long long ans =1001001001001001;
    for(int i = 0; i + k - 1 < n; i++){
        long long ABS = dist.at(i + k - 1) - dist.at(i);
        if(dist.at(i) >= 0) ans = min(ans, dist.at(i) + ABS);
        else if(dist.at(i + k - 1) <= 0) ans = min(ans, ABS - dist.at(i + k - 1));
        else ans = min(ans, ABS + min(abs(dist.at(i)), dist.at(i + k - 1)));
    }
    cout << ans << endl;

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
      // #ifndef ONLINE_JUDGE
      //  // for getting input from input.txt
      //  freopen("input.txt", "r", stdin);
      //  // for writing output to output.txt
      //  freopen("output.txt", "w", stdout);
      // #endif
       ll n,ans=0;
       cin>>n;
       vector<ll> a(n+2,0);
       vector<ll> b(n+1,0);
       for (int i = 1; i <= n+1; ++i)
       {
         cin>>a[i];
       }
       for (int i = 1; i <= n; ++i)
       {
         cin>>b[i];
       }
       for (int i = 1; i <= n; ++i)
       {
         ll v = min(a[i],b[i]);
         a[i] =a[i] -v;
         b[i] =b[i] -v;
         ll x = min(a[i+1],b[i]);
        a[i+1] = a[i+1] - x;
        b[i] = b[i] - x;
        ans = ans + (x+v );
       }

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


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

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

using namespace std;

int main(){
  string a,b,c;
  cin>>a>>b>>c;
  
  if(a.at(a.size()-1)==b.at(0) && b.at(b.size()-1)==c.at(0)){
    cout<<"YES";
  }else{
    cout<<"NO";
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
 
int main()
{
int n,w;
cin>>n>>w;
int val[n],we[n];
  
  for(int i=0;i<n;i++)
  cin>>we[i]>>val[i];
   
 ll dp[n+1][w+1];
          
          for(int i=0;i<=n;i++)
          {
             for(int j=0;j<=w;j++)
             {
               if(i==0||j==0)
                 dp[i][j]=0;
               
               else if(we[i-1]<=j)
               dp[i][j]=max(dp[i-1][j],dp[i-1][j-we[i-1]]+val[i-1]);
               
               else
                 dp[i][j]=dp[i-1][j];
                 
             
             }
          }
          
          cout<<dp[n][w];
return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define REP(...) _overload3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

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

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl


int main(){
    int n;
    cin>>n;
    ll c[5]={};
    REP(i,n){
        string s;
        cin>>s;
        switch(s[0]){
            case 'M':c[0]++;break;
            case 'A':c[1]++;break;
            case 'R':c[2]++;break;
            case 'C':c[3]++;break;
            case 'H':c[4]++;break;
        }
    }
    /*REP(i,5){
        cout<<c[i]<<endl;
    }*/
    ll ans=0;
    ans+=c[0]*c[1]*c[2];
    ans+=c[0]*c[1]*c[3];
    ans+=c[0]*c[1]*c[4];
    ans+=c[0]*c[2]*c[3];
    ans+=c[0]*c[2]*c[4];
    ans+=c[0]*c[3]*c[4];
    
    ans+=c[1]*c[2]*c[3];
    ans+=c[1]*c[2]*c[4];
    ans+=c[1]*c[3]*c[4];
    
    ans+=c[2]*c[3]*c[4];

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


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

int main(){
	int n, score=0, out=0;
	int rui[4];
	string s;

	for(int i=0 ; i<4 ; i++){
		rui[i] = (i==0)? 1 : 0 ;
	}
	cin >> n ;
	
	while( n > 0 ){
		
		cin >> s;
		if( s == "HIT" ){
			if( rui[1] == 1 ){
				if( rui[2] == 1 ){
					( rui[3] == 1 )? score++ : rui[3] = 1 ;
				}else{
					rui[2] = 1;
				}
			}else{
				rui[1] = 1;
			}
		}else if( s == "OUT" ){
			out++;
		}else if( s == "HOMERUN" ){
			for(int i=0 ; i<4 ; i++){
				score += rui[i];
				if(i>=1) rui[i] = 0;
			}
		}
			
		if(out==3){
			out = 0;
			n--;
			for(int i=0 ; i<4 ; i++){
				rui[i] = (i==0)? 1 : 0 ;
			}
			cout << score << endl;
			score = 0;
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <algorithm>

using namespace std ;

int dp[ 100007 ] ;

int main( void ) {
        int n, w, mx ;
        scanf( "%d %d", &n, &w ) ;
        dp[ 0 ] = 0 ;
        mx = n * 1000 ;
        for( int i = 1 ; i <= mx ; ++i ) dp[ i ] = w + 1 ;
        for( int num = n; num--; ) {
                int wt, val ;
                scanf( "%d %d", &wt, &val ) ;
                for( int i = mx ; i >= val ; --i ) {
                        dp[ i ] = min( dp[ i ], dp[ i - val ] + wt ) ;
                }
        }
        for( int i = mx ; i >= 0 ; --i ) {
                if( dp[ i ] <= w ) {
                        printf( "%d\n", i ) ;
                        break ;
                }
        }
        return 0 ;
}


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

using namespace std;

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

  vector<int> A;
  int sum = 0;
  for(int i = 0;i < N;++i){
    int temp;
    cin>>temp;
    A.push_back(temp);
    sum += temp;
  }

  int day = sum / N;
  while(1){
    int c = 0;
    int a = 0;
    for(int e : A){
      c = (c + e) - day;
      if(c < 0){
        --day;
        a = 1;
        break; 
      } 
    }
    if(a == 0){
      break;
    }
    else{
      a = 0;
    }
  }

  cout<<day<<endl;

  return 0;
}


Measured memory_bytes: 3152
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<algorithm>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;

P ab[500005];
int r[500005];

signed main() {
	int n; cin >> n;
	rep(i, n) {
		int a, b; cin >> a >> b; ab[i] = P(a, b);
	}
	sort(ab, ab + n);

	rep(i, n)r[i + 1] = ab[i].second;
	rep(i, n)r[i + 1] += r[i];
	int ans = 0;
	int m = r[0] - ab[0].first;
	for (int i = 0; i<n; i++) {
		int M = r[i + 1] - ab[i].first;
		m = min(r[i]-ab[i].first, m);
		ans = max(ans, M - m);

	}
	cout << ans << endl;
}


Measured memory_bytes: 14812
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; (i)<(n); ++(i))
#define reps(i,s,n) for(int i=(s); (i)<(n); ++(i))
#define maxi(v) distance(v.begin(), max_element(v.begin(), v.end()))
#define mini(v) distance(v.begin(), min_element(v.begin(), v.end()))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
  }
int main(){
    int n,q; cin >> n >> q;
    string s; cin >> s;
    vector<int> l(q), r(q); rep(i,q) cin >> l[i] >> r[i];
    vector<int> v(n,0);
    rep(i,n) if(s[i]=='A'&&s[i+1]=='C') v[i]++;
    int max = accumulate(v.begin(), v.end(), 0);
    rep(i,q) {
      int ans = 0;
      if(r[i]-l[i]<n/2) ans = accumulate(v.begin()+l[i]-1, v.begin()+r[i]-1, 0);
      else ans = max - accumulate(v.begin(), v.begin()+l[i]-1, 0) - accumulate(v.begin()+r[i]-1, v.end(), 0);
      cout << ans << endl;
 
    }


    return 0;
}


Measured memory_bytes: 2176
<?php
list($n, $k) = explode(" ", trim(fgets(STDIN)));
$array = explode(" ", trim(fgets(STDIN)));
$min = 100000000000;
for($i = 0; $i < $n - $k + 1; $i++){
    $min = min($min, abs($array[$i]) + abs($array[$i] - $array[$i + $k - 1]));
    $min = min($min, abs($array[$i + $k - 1]) + abs($array[$i] - $array[$i + $k - 1]));
}
echo $min;


Measured memory_bytes: 12792
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iomanip>    // fixed, setprecision
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  ll N, c = 0, a;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a;
    if (i % 2 == 0 && a % 2 == 1) c++;
  }
  cout << c << endl;
}


Measured memory_bytes: 3116
#高速素因数分解  osa_k法 
def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    MAXN =10**6 +10
    #osa_k法
    sieve = [i for i in range(MAXN+1)]
    p = 2
    while p*p <= MAXN:
        if sieve[p] == p:
            for q in range(2*p,MAXN+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break #共通要素があったらpair_wではない→set_w
        used |=aa
    
print(ans)

Measured memory_bytes: 127776
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)

D = defaultdict(int)
for i in A:
	D[i] += 1

d = []
for i in D:
	d.append(D[i])

ans = N
n = len(d)
if (N - n) % 2 == 0:
	print(n)
else:
	print(n - 1)

Measured memory_bytes: 18640
# coding: utf-8

# https://atcoder.jp/contests/abc118


def main():
    N = int(input())
    A = list(map(int, input().split()))

    def gcd(n, m):
        """
        2020/05/22
        """
        while True:
            if m == 0:
                return n
            n, m = m, n % m

    for i in range(N-1):
        A[i+1] = gcd(A[i], A[i+1])

    return A[i+1]


print(main())


Measured memory_bytes: 20040
<?php
fscanf(STDIN, "%d", $N);
$ans = array_fill(1, $N, 0);
$ub = intval(sqrt($N));
for ($x = 1; $x < $ub; $x++) {
    for ($y = 1; $y < $ub; $y++) {
        for ($z = 1; $z < $ub; $z++) {
            $t = $x * $x + $y * $y + $z * $z + $x * $y + $y * $z + $z * $x;
            if ($t <= $N) {
                $ans[$t]++;
            }
        }   
    }    
}
echo implode(PHP_EOL, $ans);


Measured memory_bytes: 16440
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n,m;
  cin>>n>>m;
  cout<<n*(n-1)/2 + m*(m-1)/2;
  
   
   
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int a, b, c, i;
	
	scanf("%d %d %d\n", &a, &b, &c);
	
	if(a>b){
		i=a;
		a=b;
		b=i;
	}
	if(b>c)
	{
		i=b;
		b=c;
		c=i;
	}
	
	if(a>b){
		i=a;
		a=b;
		b=i;
	}
	
	printf("%d %d %d\n", a, b, c);
	return 0;
}


Measured memory_bytes: 2044
is_prime = ->(n) {
  if n == 1 then
    return false
  elsif n == 2 then
    return true
  else
    lim = Math.sqrt(n).to_i + 1
    (2..lim).each do |i|
      if n % i == 0
        return false
      end
    end
    return true
  end
}

res = 0
while line = gets
  n = line.chomp.to_i
  if is_prime.call(n) then
    res += 1
  end
end
puts res

Measured memory_bytes: 8852
#include<stdio.h>
#include<string.h>
int main(void){
int n,Ttarou=0,Thanako=0;
char tarou[100],hanako[100];
scanf("%d",&n);
for(int a=0;a<n;a++){
scanf("%s",tarou);
scanf("%s",hanako);
if(strcmp(tarou,hanako)==0){Ttarou++;Thanako++;}
else if(strcmp(tarou,hanako)>0)Ttarou+=3;
else if(strcmp(tarou,hanako)<0)Thanako+=3;
}
printf("%d %d\n",Ttarou,Thanako);
return 0;
}


Measured memory_bytes: 2028
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    int a = s - 9 * (s / 100) - 9 * (s / 10);
    System.out.println(a);
    sc.close();
  }
}


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

int main() {
	int cnt[30];
	char s[10];
	bool valid = true;
	scanf("%s", s);
	memset(cnt, 0, sizeof cnt);
	for (int i = 0; i < 4; i++)
		cnt[s[i] - 'A']++;
	for (int i = 0; i < 26; i++)
		if ((cnt[i] != 2) && (cnt[i] != 0))
			valid = false;
	if (valid)
		puts("Yes");
	else
		puts("No");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
	int A, B, C;

	cin >> A >> B >> C;

	if (A == B)
		cout << C << endl;
	else if (A == C)
		cout << B << endl;
	else if (B == C)
		cout << A << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int H, W, Q;
char map[2005][2005];

int vsumX[2005][2005], vsum[2005][2005];
int exsumX[2005][2005], exsum[2005][2005];
int eysumX[2005][2005], eysum[2005][2005];

int main(void)
{
	cin >> H >> W >> Q;
	for(int y = 1; y <= H; y++){
		for(int x = 1; x <= W; x++){
			cin >> map[x][y];
		}
	}
	
	for(int y = 1; y <= H; y++){
		for(int x = 1; x <= W; x++){
			vsumX[x][y] = vsumX[x-1][y];
			if(map[x][y] == '1') vsumX[x][y]++;
		}
	}
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			vsum[x][y] = vsum[x][y-1] + vsumX[x][y];
		}
	}
	
	for(int y = 1; y <= H; y++){
		for(int x = 1; x <= W; x++){
			exsumX[x][y] = exsumX[x-1][y];
			if(map[x][y] == '1' && map[x+1][y] == '1') exsumX[x][y]++;
		}
	}
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			exsum[x][y] = exsum[x][y-1] + exsumX[x][y];
		}
	}
	
	for(int y = 1; y <= H; y++){
		for(int x = 1; x <= W; x++){
			eysumX[x][y] = eysumX[x-1][y];
			if(map[x][y] == '1' && map[x][y+1] == '1') eysumX[x][y]++;
		}
	}
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			eysum[x][y] = eysum[x][y-1] + eysumX[x][y];
		}
	}
	
	int x1, y1, x2, y2;
	for(int q = 0; q < Q; q++){
		cin >> y1 >> x1 >> y2 >> x2;
		int v = vsum[x2][y2] - vsum[x2][y1-1] - vsum[x1-1][y2] + vsum[x1-1][y1-1];
		int ex = exsum[x2-1][y2] - exsum[x2-1][y1-1] - exsum[x1-1][y2] + exsum[x1-1][y1-1]; 
		int ey = eysum[x2][y2-1] - eysum[x2][y1-1] - eysum[x1-1][y2-1] + eysum[x1-1][y1-1]; 
		cout << v - ex - ey << endl;
	}
	return 0;
}

Measured memory_bytes: 99968
N=int(input())
l=list(map(int,input().split()))
d={}
for j in range(N):
	if l[j] not in d:
		d[l[j]]=0
	d[l[j]]+=1
ans=sum(l)
Q=int(input())
for i in range(Q):
	B,C=map(int,input().split())
	if B in d:
		v=d[B]
		if C in d:
			d[C]+=d[B]
		else:
			d[C]=d[B]
		del(d[B])
		ans+=(C-B)*v
	print(ans)

Measured memory_bytes: 20516
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll MOD=1e9+7;

ll gcd(ll x,ll y){
    if(y==0) return 0;
    return gcd(y,x%y);
}

int dis2(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int main(){
    string s;cin>>s;
    if(s=="hi"||s=="hihi"||s=="hihihi"||s=="hihihihi"||s=="hihihihihi"){
        cout<<"Yes"<<endl;
    }else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    char s[3],t[3];
    int ans=0;
    for(int i=0;i<3;i++)cin>>s[i];
    for(int i=0;i<3;i++){
        cin>>t[i];
        ans+=t[i]==s[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
class Cell 
  attr_reader :x, :y, :cost, :goal, :eval
  
  def initialize(x, y, c)
    @x = x
    @y = y
    @cost = c
    @goal = $w - 1 - x + $h - 1 - y
    @eval = @cost + @goal
  end
end
 
class PriorityQueue
  attr_reader :elements
  
  def initialize
    @elements = []
  end
 
  def push(n)
    i = @elements.size
    while i > 0
      p = (i-1) / 2
      break if @elements[p].eval <= n.eval
      @elements[i] = @elements[p]
      i = p
    end
    @elements[i] = n
  end
  alias :<< :push
  
  def pop
    min = @elements[0]
    n   = @elements.pop
    unless @elements.empty?
      i = 0
      while i * 2 + 1 < @elements.size
        if @elements[i * 2 + 2].nil? or @elements[i * 2 + 1].eval < @elements[i * 2 + 2].eval
          buf = i * 2 + 1
        else
          buf = i * 2 + 2
        end
        break if @elements[buf].eval >= n.eval
        @elements[i] = @elements[buf]
        i = buf
      end
      @elements[i] = n
    end
    min
  end
  
  def empty?
    @elements.empty?
  end
end
 
$h, $w = gets.chomp.split.map(&:to_i)
matrix = Array.new($h) { gets.chomp.split("").map{ |x| x == "." ? 0 : 1 } }
 
opened = Array.new($h) { Array.new($w, false) }
 
x, y, cost = 0, 0, 0
opened[y][x] = true
queue = PriorityQueue.new
queue << Cell.new(x, y, 1)
until [x, y] == [$w-2, $h-1] or [x, y] == [$w-1, $h-2]
  cell = queue.pop
  x, y, c = cell.x, cell.y, cell.cost
  
  if x+1 <= $w-1 and matrix[y][x+1] == 0 and !opened[y][x+1]
    queue << Cell.new(x+1, y, c+1)
    opened[y][x+1] = true
  end
  
  if x-1 >= 0 and matrix[y][x-1] == 0 and !opened[y][x-1]
    queue << Cell.new(x-1, y, c+1)
    opened[y][x-1] = true
  end
  
  if y+1 <= $h-1 and matrix[y+1][x] == 0 and !opened[y+1][x]
    queue << Cell.new(x, y+1, c+1)
    opened[y+1][x] = true
  end
  
  if y-1 >= 0 and matrix[y-1][x] == 0 and !opened[y-1][x]
    queue << Cell.new(x, y-1, c+1)
    opened[y-1][x] = true
  end
=begin
  [[1,0], [-1,0], [0,1], [0,-1]].each do |dx, dy|
    puts "x=#{x},y=#{y},dx=#{dx},dy=#{dy}"
    if (x+dx).between?(0, $w-1) and (y+dy).between?(0, $h-1) and !opened[y+dy][x+dx]
      puts "ok"
      queue << Cell.new(x+dx, y+dy, c+1)
      opened[y+dy][x+dx] = true
    end
  end
=end
  cost = c+1
  
  if queue.empty?
    puts -1
    exit
  end
end
puts matrix.flatten.select { |x| x == 0 }.size - cost

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define RFOR(i, b, a) for (ll i = b; i >= a; --i)
#define ALL(x) x.begin(), x.end()
#define DEBUG(args...) { string _s = #args; replace(ALL(_s), ' ', '\0');\
replace(ALL(_s), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); _debug(_it, args);}
#define endl "\n"
#define F first
#define S second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void _debug(istream_iterator<string>) {}
template<typename T, typename... Args>
void _debug(istream_iterator<string> it, T first, Args... args) {
    cerr << ">> " << *it << " : " << first << endl; _debug(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "(" << p.F << ", " << p.S << ")";
}
template<typename T>
inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty()) return out << "[]";
    else { out << '['; for (auto& e : v) { out << e << ", "; } return out << "\b\b]"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const set<T>& s) {
    if (s.empty()) return out << "{}";
    else { out << '{'; for (auto& e : s) { out << e << ", "; } return out << "\b\b}"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const unordered_set<T>& s) {
    return out << set<T>(ALL(s));
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const map<T1, T2>& m) {
    if (m.empty()) return out << "{}";
    out << '{'; for (auto& p : m) { out << p << ", "; } return out << "\b\b}";
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const unordered_map<T1, T2>& m) {
    return out << map<T1, T2>(ALL(m));
}
template<typename T>
inline ostream& operator << (ostream& out, const ordered_set<T>& s) {
    return out << set<T>(ALL(s));
}

typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef unordered_map<ll, ll> STll;
/************************************** MAIN PROGRAM ********************************************/

int main()
{
   // freopen("input.txt", "r", stdin);
    SPEED
    ll n;
    cin >> n;
    cout << n * (n - 1) / 2;
}
/************************************** END OF PROGRAM ******************************************/
/** Stuff you should look for:
 * int overflow, array bounds, over-counting, graph is not a tree/connected
 * special cases (n=1?), set/unordered_set TLE, multi-set/set error
 * do something instead of nothing and stay organized
 */


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

int main() {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    string newS = "";

    for(int i=0;i<N;i++){
        if(i == K-1){
            S[i] = S[i] + 0x20;
        }
    }
    cout << S << endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N,Y;
 cin >>  N >>Y;
int i,j;
 int ta = -1; int tb = -1; int tc = -1; 
  
  for (int i = 0; i <= N; i++){
    for (int j = 0; i+j <= N; j++){
      int k = N - i - j;
     if(i *10000 + j*5000 + (N - i - j)*1000 == Y){
     ta = i;
     tb = j;
     tc = N - i - j;}
 
     }
 }
 
 
 cout <<  ta  << " " << tb <<  " " << tc << endl;
}

Measured memory_bytes: 256
n = int(input())
a_list = list(map(int,input().split()))
sum_a = sum(a_list)

sum = 0
for i in range(n):
  sum += a_list[i] * (sum_a-a_list[i])
  sum = sum%(10**9+7)
  sum_a -= a_list[i]
print(sum)

Measured memory_bytes: 94280
import java.util.Scanner;

public class Main {
    public static void main(String[] args ){
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        if(a > b){
            System.out.println("a > b");
        }
        else if(a < b){
            System.out.println("a < b");
        }
        else{
            System.out.println("a == b");
        }
    }
}




Measured memory_bytes: 26160
#include <stdio.h>

int main(void)
{
	int i, j, a, b[10000];

	i = 0;

	scanf("%d", &a);
	
	while(a != 0)
	{
		b[i] = a;
		i++;
		scanf("%d", &a);
	}

	for(j=0;j<i;j++)
	{
		printf("Case %d: %d\n", j+1, b[j]);
	}

	return 0;
}

Measured memory_bytes: 636
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;
template<typename T>
T gcd(T a, T b){
    return b ? gcd(b, a % b) : a;
}    

int main(){ 
    double t,x;
    cin >> t >> x;
    cout  << t/x << endl;
    
    return 0;
}


    
    

   


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define trav(x,v) for(auto &x : (v))
#define all(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

typedef long double ld;

const int junk = 37;

template<typename T>
void shft(vector<T> &v, int i){
	vector<T> u(sz(v));
	rep(j,0,sz(v)) u[j] = v[ (i+j) % sz(v)];
	swap(v, u);
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n;
	cin >> n;

	vector<ll> a(n);
	vi b(n);
	trav(x, a) cin >> x;
	trav(x, b) cin >> x;

	int i = 0;
	rep(j,1,n) if(a[j] > a[i]) i = j;

	shft(a, i);
	shft(b, i);
	// now a[0] is maximal. Push it to back as well
	
	b[0] = junk;
	a.push_back(a[0]);
	b.push_back(junk);

	vector<ld> x(n);
	rep(i,1,n) x[i] = 2 / (1/ld(i) + 1/ld(n-i));

	// expected value
	vector<ld> xp(n+1, a[0]);
	rep(i,1,n) xp[i] -= x[i] * b[i];

	ld cur = 0, sub = 0;
	rrep(i,1,n){
		cur -= sub;
		xp[i] -= cur;
		cur += x[i] * b[i];
		sub += x[i] * b[i] / ld(i);
	}
	cur = 0, sub = 0;
	rep(i,1,n){
		cur -= sub;
		xp[i] -= cur;
		cur += x[i] * b[i];
		sub += x[i] * b[i] / ld(n-i);
	}

	// naive quadratic algo
	function<void(int,int)> rek = [&](int fr, int to){
		if(fr + 1 == to) return;	

		int i = fr+1;
		// find position with biggest loss
		rep(j,i+1,to) if( a[j]-xp[j] > a[i]-xp[i] ) i = j;

		ld dif = a[i] - xp[i];
		if(dif <= 0) return;

		rep(j, fr, to) xp[j] += dif * (1 - abs(i-j) / ld(i > j ? i-fr : to-i));
		rek(fr, i);
		rek(i, to);
	};
	rek(0,n);

	ld avg = 0;
	rep(i,0,n) avg += xp[i];
	avg /= n;

	cout.precision(13);
	cout << avg << endl;
}


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

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int a, b, k;
  cin >> a >> b >> k;

  int num = 0;
  int ans = -1;

  vector<int> v;
  for(int i = 100; i >= 1; --i){
    if(a % i == 0 && b % i == 0){
      num++;
      if(num == k){
        ans = i;
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <map>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
int main(){
 
int n;
cin >> n;
 
ll MARCH[5] = {};
 
for(int i = 0; i<n; i++){
string s;
cin >> s;
 switch ( s[0] )  {  
case 'M':  
MARCH[0]++;  
break;  
case 'A':  
MARCH[1]++;  
break;  
case 'R':  
MARCH[2]++;  
break;  
case 'C':  
MARCH[3]++;  
break;  
case 'H':  
MARCH[4]++;  
break;  
      } 
}
 
ll ans = 0;
 
for(int i = 0; i<5; i++){
 for(int j = i+1; j < 5;j++){
   for(int k = j+1; k < 5;k++){
ans += MARCH[i]* MARCH[j]* MARCH[k];
  }
 }
}
 
cout << ans << endl;
 
return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int cnt = 0;
        for(int i = a; i <= b; i++) {
            if(isPalin(i)) cnt++;
        }
        System.out.println(cnt);
    }

    private static boolean isPalin(int num) {
        if(num % 10 == 0) return false;
        int originalNum = num;
        int n = 0;
        while(num > 0) {
            n = n * 10 + num % 10;
            num /= 10;
        }
        return n == originalNum;
    }
}


Measured memory_bytes: 24020
#include <stdio.h>
 
int main(void){
  char s[11], t[11];
  scanf("%s %s", &s, &t);
  int a, b;
  scanf("%d %d", &a, &b);
  char u[11];
  scanf("%s", &u);
  
  if (strcmp(s, u) == 0){
    printf("%d %d", a-1, b);
  }else{
    printf("%d %d", a, b-1);
  }
  return 0;
}

Measured memory_bytes: 128
while True:
    n,m = map(int,input().split())
    if n == m == 0: break
    c1 = [int(input()) for i in range(n)]
    c2 = [int(input()) for i in range(m)]
    diff = sum(c1) - sum(c2)
    if diff % 2 == 1:
        print(-1)
        continue
    for v1 in sorted(c1):
        v2 = v1 - diff//2
        if v2 in c2:
            print('{0} {1}'.format(v1, v2))
            break
    else:
        print(-1)

Measured memory_bytes: 5604
MOD = (10**9) + 7
ONE = '1'.freeze
 
def nCk(n, k)
  (fact(k + 1, n) * inv(fact(1, n - k) % MOD)) % MOD
end
 
def fact(s, e)
  (s..e).reduce(1) { |r, i| (r * i) % MOD }
end
 
def inv(x)
  res = 1
  beki = x
  (MOD - 2).to_s(2).reverse.chars do |digest|
    res = (beki * res) % MOD if digest == ONE
    beki = (beki * beki) % MOD
  end
  res
end

X, Y = gets.split.map(&:to_i)

if (X + Y) % 3 != 0
  puts 0
  exit
end

m = (2 * X - Y) / 3
n = X - 2 * m

if m < 0 || n < 0
  puts 0
  exit
end
puts nCk(n + m, n)

Measured memory_bytes: 1788
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint dp[5010][5010];
lint inf=123456789012345678LL;
int p[5010];
int main()
{
	int n;lint a,b;
	cin>>n>>a>>b;
	rep(i,n) cin>>p[i];
	rep(i,5005) rep(j,5005) dp[i][j]=inf;dp[0][0]=0;
	rep(i,n) rep(j,n+1){
		if(dp[i][j]>=inf) continue;
		//cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
		if(p[i]>j){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a);
			dp[i+1][p[i]]=min(dp[i+1][p[i]],dp[i][j]);
		}
		else if(p[i]<j){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+b);
		}
		else{
			assert(false);
		}
	}
	lint out=inf;
	rep(i,n+1) out=min(out,dp[n][i]);
	cout<<out<<endl;
}


Measured memory_bytes: 196224
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    A, B, C = map(int, sys.stdin.readline().split())
    print(max(0, C -(A - B)))


Measured memory_bytes: 5712
#include<bits/stdc++.h>
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;

using ll = long long;


ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r;
string s, t, u;
ll v, w, x, y, z;

int main() {
    
    cin >> a >> b >> c;

    cout << (a+b+c >= 22 ? "bust" : "win") <<endl;


}




Measured memory_bytes: 3628
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    double L;
    cin >> L;
    cout << setprecision(10) << pow(L/3.0, 3.0) << endl;
}


Measured memory_bytes: 3752
import java.io.PrintWriter
import java.util.*

object out : PrintWriter(System.out)

fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val a = IntArray(n) { readLine()!!.toInt() }
    val m = arrayOf(HashMap<Int, Int>(), HashMap<Int, Int>())
    a.forEachIndexed { i, a -> m[i % 2][a] = (m[i % 2][a] ?: 0) + 1 }
    a.sort()
    a.forEachIndexed { i, a -> m[i % 2][a] = (m[i % 2][a] ?: 0) - 1 }
    out.println(m[0].values.map { Math.max(it, 0) }.sum())
    out.close()
}

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

int A[20];
int x[20][20], y[20][20];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    int ans = 0;
    
    for(int i = 0; i < N; i++){
        cin >> A[i];
        for(int j = 0; j < A[i]; j++){
            cin >> x[i][j] >> y[i][j];
            x[i][j]--;
        }
    }

    for(int bit = 0; bit < (1 << N); bit++){
        bool flag = true;
        for(int i = 0; i < N; i++){
            if(bit & (1 << i)){

                for(int j = 0; j < A[i]; j++){
                    if((y[i][j] == 0) && (bit & (1 << x[i][j])) != 0) flag = false;
                    if((y[i][j] == 1) && (bit & (1 << x[i][j])) == 0) flag = false;
                }
            }
        }
        if(flag){
                    ans = max(ans, __builtin_popcount(bit));
                }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define pdump(p) cout<<" "<<#p<<"=("<<p.fst<<","<<p.snd<<")"
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std; using lint = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<lint, lint>;

int main(void) {
    int n;
    cin >> n;
    double sum = 0.0;
    rep (n) {
        double d; string s;
        cin >> d >> s;
        if (s == "JPY") {
            sum += d;
        }
        else {
            sum += (d * 380000.0);
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256