akhauriyash/Code-Regression huggingface dataset:
/*input
2 3 2 0
*/

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

#define Fi              first
#define Se              second
#define S(n)            cin >> n
#define P(n)            cout << n
#define pb              push_back
#define pp              pop_back
#define pf              pop_front
#define sp              cout << " "
#define nl              cout << "\n"
#define MIN(con)        (*min_element(ALL(con))) 
#define MAX(con)        (*max_element(ALL(con)))
#define mem(n, a)       memset((n), (a), sizeof(n))
#define ALL(cont)       (cont).begin(),(cont).end()
#define NX(cont)        next_permutation(ALL(cont))
#define PX(cont)        prev_permutation(ALL(cont))
#define F(i, n, r)      for(int i = (n); i < (r); i ++)
#define prec(n)         cout << fixed << setprecision(n)
#define PI              3.14159265358979323846264338327951
#define fast            ios_base:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FH(it,c)   for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++ it)
 
using ll = long long;
using ss = stringstream;
using ul = unsigned long long;
 
template < typename T > inline T LCM(T a, T b)            { return (a * b) / GCD(a, b); }
template < typename T > inline T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > inline T _max(T a, T b, T c)      { return max( max( a, b ), c ); }
template < typename T > inline T _min(T a, T b, T c)      { return min( min( a, b ), c ); }
template < typename T > inline string toString(T a)       {return to_string(a); }  // Convert int to string
template < typename T > inline void toInt(string s, T &x) { ss str(s); str >> x;}  // Convert string to int

inline void lower(string &s) { 
  FH(it,s) 
    *it = tolower(*it); 
} 
 
inline void upper(string &s) { 
  FH(it,s) 
    *it = toupper(*it); 
}

const ll inf    =  1e18;
const ll M = 1e9 + 7;

bool palin(string s)
{
    string s1 = s;
    reverse(s.begin(), s.end());
    return (s == s1);
} 

ll triangle(ll n)
{
    return (n * (n + 1)) / 2;
}

bool check(ll n) 
{
    if(n == 1) return 0;
    if(n == 2 or n == 3) return 1;
    if(n % 2 == 0 or n % 3 == 0) return 0;

    for(ll i = 5; i * i <= n; i += 6) if(n % i == 0 or n % (i + 2) == 0) return 0;
    return 1;
}

int main ()
{
    fast;
    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    if(!k) {
        return cout << a - b, nl, 0;
    }
    ll x = b + c;
    ll y = a + c;

    if(k % 2 == 0) {
        x += 2 * a;
        y += 2 * b;
    }

    ll val = x - y;
    if(val > 1e18) {
        cout << "Unfair";
    }
    else cout << val;
    nl;    
    return 0;
}


Measured memory_bytes: 256
def geq(ga, gb, m, bi, bj)
  (0...m).each do |i|
    (0...m).each do |j|
      if (ga[bi+i][bj+j] != gb[i][j])
        return false
      end
    end
  end
  return true
end

def solve
  n,m = gets.scan(/-?[\d\.]+/).map(&:to_i)
  a = Array.new(n)
  b = Array.new(m)
  n.times do |i|
    a[i] = gets
  end
  m.times do |i|
    b[i] = gets
  end

  (0..(n-m)).each do |bi|
    (0..(n-m)).each do |bj|
      if geq(a, b, m, bi, bj)
        puts "Yes"
        return
      end
    end
  end

  puts "No"
end

solve


Measured memory_bytes: 3836
A, B, M = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)
bs = gets.split.map(&:to_i)

res = as.min + bs.min

M.times do |i|
  x, y, c = gets.split.map(&:to_i)
  sale = as[ x-1 ] + bs[ y-1 ] - c
  res = sale if sale < res
end

puts res


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)
#define AMX 1505050
ll N,A[505050];
ll mk1[AMX];
ll mk2[AMX];
ll mk4[AMX];
ll dp[AMX];
ll zp[505050];
ll i, j, k, l,ans;
int main(){
    scanf("%lld", &N);
    fornum(i,0,N){
        scanf("%lld", &A[i]);
    }
    fornum(i,0,N){
        k ^= A[i];
        if(k==0){
            zp[i + 1]++;
        }
        zp[i + 1] += zp[i];
    }
    /*
    for (i = N - 1; i >= 0;i--){
        zp[i] += zp[i + 1];
    }

    fornum(i,0,N){
        printf("%lld ", zp[i+1]);
    }*/
    j = 0;
    fornum(i,0,N){
        j ^= A[i];
        if(mk2[j]!=zp[i+1]){
            mk4[j] = (mk4[j]+mk1[j]*(zp[i+1]-mk2[j])%MOD)%MOD;
            mk2[j] = zp[i+1];
            //mk1[j] = 0;
        }
        mk1[j]=(mk1[j]+mk4[j]+1)%MOD;
        //dp[j] = (dp[j] + mk3[j]) % MOD;
        //printf("%lld,%lld,%lld\n", j,mk1[j], mk4[j]);
    }
    if(j!=0){
        //printf("%llda\n", j);
        ans = (mk4[j]+1) % MOD;
    }else{
        ans = 1;
        fornum(i,1,mk2[0]){
            ans = (ans * 2) % MOD;
        }
        fornum(i,1,AMX){
            ans = (ans + mk1[i]) % MOD;
            //printf("%lld,%lldb\n",i, dp[i]);
        }
        //ans = ans % MOD;
    }
    printf("%lld", ans);
    return 0;
}

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

int		main(void)
{
	int N, L;

	cin >> N >> L;
	vector<string> S(N);
	for (int i = 0; i < N; i++)
		cin >> S[i];
//	string tmp;
//	int min;
//
//	for (int i = 0; i < N - 1; i++)
//	{
//		min = i;
//		for (int j = i + 1; j < N; j++)
//		{
//			if (strcmp(S[min].c_str(), S[j].c_str()) > 0)
//				min = j;
//		}
//		tmp = S[i];
//		S[i] = S[min];
//		S[min] = tmp;
//	}
	sort(S.begin(), S.end());
	for (int i = 0; i < N; i++)
		cout << S[i];
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    for (int i = 1; i <= 1000000; i++) {
        int c = (int)(floor(i * 0.08) + 1e-9);
        int d = (int)(floor(i * 0.1) + 1e-9);
        if (c == a && d == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}


Measured memory_bytes: 3644
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int team1;
		int team2;
		int point1;
		int point2;
		int[] win=new int[100];
		int[] total=new int[100];
		int N=n*(n-1)/2;
		for(int i=0;i<N;i++){
			team1=sc.nextInt();
			team2=sc.nextInt();
			point1=sc.nextInt();
			point2=sc.nextInt();
			if(point1>point2){
				win[team1-1]=win[team1-1]+3;
			}
			else if(point1<point2){
				win[team2-1]=win[team2-1]+3;
			}
			else{
				win[team1-1]=win[team1-1]+1;
				win[team2-1]=win[team2-1]+1;
			}
		}
		for(int a=0;a<n;a++){
			int r = 1;
			for(int j=0;j<n;j++){
				if(win[a]<win[j]){
					r = r + 1;
				}
				
			}
			total[a] = total[a] + r;
			
		}
		for(int b = 0; b < n; b++){
			System.out.println(total[b]);
			
		}
	}
}

Measured memory_bytes: 41960
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, rate, min = 0, max = 0;
  cin >> N;
  vector<int> v(N);
  vector<int> color(9,0);
  for(int i=0;i<N;i++){
    cin >> v.at(i);
  }
  for(int i=0;i<N;i++){
    rate = v.at(i) / 400;
    if(rate >= 9){
      color.at(8) += 1;
    }else{
      color.at(rate) += 1;
    }
  }
  for(int i=0;i<9;i++){
    if(color.at(i)){
      if(i==8){
        if(min == 0){
          ++min;
        }
        max += color.at(i);
      }else{
        ++min;
        ++max;
      }
    }
  }
  cout << min << " " << max << endl;
}

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

#define inf 0x3f3f3f3f
#define INF 1000111000111000111LL
#define mod 1000000007
#define pi acos(-1.0)
#define eps 1e-8
#define endl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define all(cc) (cc).begin(),(cc).end()
using lli = long long int ;
using pii = pair<int, int> ;
using vi = vector<int> ;
using vb = vector<bool> ;
using vvi = vector<vector<int>> ;
using vlli = vector<long long int> ;
using vpii = vector<pair<int, int>> ;

int main()
  {
    ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
    lli n, tot=0, x, curr ;
    cin>> n ;
    vlli a ;
    a.pb(0) ;
    for(int i=1 ; i<=n ; i++) cin>> x, a.pb(x) ;
    for(int i=1 ; i<=n ; i++) tot+=abs(a[i]-a[i-1]) ;
    tot+=abs(a[n]) ;
    for(int i=1 ; i<n ; i++)
      {
        curr=tot-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]) ;
        cout<< curr << endl ;
      }
    curr=tot-abs(a[n]-a[n-1])-abs(a[n])+abs(a[n-1]) ;
    cout<< curr << endl ;
  }


Measured memory_bytes: 2164
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
 
 
public class Main {

	static long MOD = 1_000_000_007;
	static int INF = 1_000_000_007;
	//二項係数関連ここから-----
	static boolean isPreprocessing = false;	//二項係数を計算するための前処理を行っているかどうかのフラグ
	static int MAX = 260;				//MAXまで階乗やそれらの逆元のテーブルを保持する。
	static long[] fac;	//fac[i] := i! % MOD
	static long[] inv;	//inv[i] := mod. MODにおける i の逆元
	static long[] finv;	//finv[i] := mod. MODにおける i! の逆元(invの累積"積")
	//二項係数関連おわり------
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		//int N = Integer.parseInt(sc.next());
		//long L = Long.parseLong(sc.next());
		//char[] A = sc.next().toCharArray();
		
		int N = Integer.parseInt(sc.next());
		int[] A = new int[N];
		int[] B = new int[N];
		int half = N/2 ;
		for(int i=0; i<N;i++){
			A[i]=Integer.parseInt(sc.next());
			if(i>=half)B[i] = A[i];
		}
		if(N==1){
			if(A[0]==1){
				System.out.println(1);
				System.out.println(A[0]);
			}else{
				System.out.println(0);
			}
		}else{
			for(int i=half; i>0; i--){
				int tmp = i;
				int ball = 0;
				tmp += i;
				while(tmp<=N){
					ball += B[tmp-1];
					tmp += i;
				}
				B[i-1] = A[i-1]^(ball%2);
			}
			
			int M = 0;
			for(int b : B){
				M += b;
			}
			System.out.println(M);
			for(int i=0; i<N; i++){
				if(B[i]==1)System.out.print((i+1) + " ");
			}
		}
		

		

		
		
	}
	
	//aとbの最小公倍数を返す
	static long lcm (long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return (c/b);
	}
	
	//二項係数用の前処理
	static void COMinit(){
		//二項係数演算用前処理
		fac = new long[MAX+1];
		fac[0] = 1L;
		fac[1] = 1L;
		inv = new long[MAX+1];
		inv[1] = 1L;
		finv = new long[MAX+1];
		finv[0] = 1L;
		finv[1] = 1L;
		for(int i=2;i<MAX;i++){
			fac[i] = fac[i-1] * i % MOD;
			inv[i] = MOD - inv[(int)(MOD%i)] * (MOD/i) % MOD;
			finv[i] = finv[i-1] * inv[i] % MOD;
		}
		isPreprocessing = true;
	}
	
	//二項係数i_C_jをMODで割った余りを返す
	static long COM(int i, int j){
		if(i<j)return 0;
		if(i<0 || j<0)return 0;
		if(!isPreprocessing)COMinit();
		return fac[i] * (finv[j] * finv[i-j] % MOD) % MOD;
	}
	
}



Measured memory_bytes: 61496
<?php
fscanf(STDIN, "%d", $count);
$key = '';
if ($count < 1 || 100 < $count) {
    exit;
}
for ($i =0; $i < $count; $i++) {
    $key .= '%s ';
}
$data = fscanf(STDIN, "$key");

$total = array_sum($data);
$avg = round($total / count($data));

$result = 0;
foreach ($data as $value) {
    if ($value < -100 || 100 < $value) {
        exit;
    }
    $result += pow(($value - $avg), 2);
}
echo $result;

?>

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
signed main(){
    int h;
    cin >> h;
    if(h == 1)
    cout << 1 << endl;
    else
    {
        int  i = 0, j = 1;
        while(1){
        j *= 2;
        if(j * 2 > h){
            h = j;
        break;
        }
        }
        int cnt = 0;
        while(1){
            if(h == 0)
            break;
            cnt += h;
            h /= 2;
        }
        cout << cnt  << endl;
    }

}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	long long int n, count=0;
	scanf("%lld", &n);
	if(n%2){
		printf("0");
		return 0;
	}else{
		n/=2;
		int y=5;
		while(n/y){
			count+=n/y;
			n/=5;
		}
		printf("%lld", count);
		return 0;
	}
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    int n,i,cnt=1;
    int a[20];
    cin >> n;
    for(i=0;i<n;i++) cin >> a[i];
    int m = a[0];
    for(i=1;i<n;i++){
        if(m<=a[i]){
            cnt++;
            m=a[i];
        }
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w;
    cin>>h>>w;
    string s[h+1];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    ll a[h+1][w+1],b[h+1][w+1],c[h+1][w+1],d[h+1][w+1];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                a[i][j]=0;
            }
            else if(j==0){
                a[i][j]=1;
            }
            else{
                a[i][j]=a[i][j-1]+1;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                b[i][j]=0;
            }
            else if(i==0){
                b[i][j]=1;
            }
            else{
                b[i][j]=b[i-1][j]+1;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=w-1;j>=0;j--){
            if(s[i][j]=='#'){
                c[i][j]=0;
            }
            else if(j==w-1){
                c[i][j]=1;
            }
            else{
                c[i][j]=c[i][j+1]+1;
            }
        }
    }
    for(int i=h-1;i>=0;i--){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                d[i][j]=0;
            }
            else if(i==h-1){
                d[i][j]=1;
            }
            else{
                d[i][j]=d[i+1][j]+1;
            }
        }
    }
    ll ans=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='.'){
                ans=max(ans,a[i][j]+b[i][j]+c[i][j]+d[i][j]-3);
            }
        }
    }
    cout << ans<<endl;
    return 0;
}



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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> hs(n);
    for(int i=0; i<n; i++) cin >> hs.at(i);
    vector<ll> node(n, static_cast<ll>(1e18));
    node.at(0) = 0;
    for(int i=0; i<n; i++)
    {
        if(i+1 < n)
        {
            ll nc = node.at(i) + abs(hs.at(i) - hs.at(i+1));
            node.at(i+1) = min(node.at(i+1), nc);
        }
        if(i+2 < n)
        {
            ll nc = node.at(i) + abs(hs.at(i) - hs.at(i+2));
            node.at(i+2) = min(node.at(i+2), nc);
        }
    }
    cout << node.back() << '\n';

    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (int)1e7;  
using  p = pair<int,int>;
using  v = vector<int>;
auto used = v(50,0);
auto a = vector<int>(50,0);
auto b = vector<int>(50,0);
auto MM = vector<v>(50,v(50,0));   
int n,m;

int main(){
   string s;
   cin >> s;
   cout<<s[0]<<s.size()-2<<s[s.size()-1]<<endl;
   return 0;
}
  
  

Measured memory_bytes: 256
def point(mid):
    ans = 0
    ans += (mid // 2) * 11
    mid -= (mid // 2) * 2
    ans += mid * 6
    return ans >= x

x = int(input())

ok = 10 ** 18
ng = 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if point(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Measured memory_bytes: 38384
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#define int long long
#define double long double
#define oku7 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用

using namespace std;
std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

vector<pair<int,int>> G[100002];

int x[100002];
int cnt = 0;
vector<pair<int, int>> inputdata;
signed main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		inputdata.push_back(make_pair(b, a));
	}
	sort(inputdata.begin(), inputdata.end());
	int before = -1;
	int ans = 0;
	for (pair<int, int> p : inputdata) {
		if (p.second <= before) continue;
		before = p.first - 1;
		ans++;
	}

	
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 4724
#include<stdio.h>

int main(void)
{
	int b;
	int f;
	int r;
	int v;
	int n;
	int room[4][3][10];
	int i;
	int j;
	int k;
	
	for(i = 0;i < 4;i++){
		for(j = 0;j < 3;j++){
			for(k = 0;k < 10;k++){
				room[i][j][k] = 0;
			}
		}
	}
	
	scanf("%d", &n);
	for(i = 0;i < n;i++){
		scanf("%d %d %d %d", &b, &f, &r, &v);
		room[b - 1][f - 1][r - 1] += v;
		if(room[b - 1][f - 1][r - 1] < 0){
			room[b - 1][f - 1][r - 1] = 0;
		}
		if(room[b - 1][f - 1][r - 1] > 9){
			room[b - 1][f - 1][r - 1] = 9;
		}
	}
	
	for(i = 0;i < 4;i++){
		for(j = 0;j < 3;j++){
			for(k = 0;k < 10;k++){
				printf(" %d", room[i][j][k]);
			}
			printf("\n");
			if(j == 2 && i != 3){
				printf("####################\n");
			}
		}
	}
	
	return (0);
}

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


int main() {
  int n, h ,w;
  cin >> n >> h >> w;
  
  int ans = (n-h+1)*(n-w+1);
  cout << ans << endl;
  
}

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

int main(){
int N,M;
cin>>N>>M;
vector<long long int>a(N);
vector<long long int>b(N);
vector<long long int>c(M);
vector<long long int>d(M);
vector<int>ans(N);

for(int i = 0;i<N;i++){
    cin>>a.at(i)>>b.at(i);
}
for(int i = 0;i<M;i++){
    cin>>c.at(i)>>d.at(i);
}
for(int i = 0; i < N;i++){
  long long int mintmp = 1000000000;
  int minind = -1;
  for(int j = 0; j < M;j++){

    long long int dist = abs(a.at(i)-c.at(j)) + abs(b.at(i)-d.at(j));
    if(mintmp>dist){
      mintmp = dist;
      minind = j+1;
    }
  }
  ans.at(i)=minind;
}
for(int i = 0;i<N;i++){
      cout<<ans.at(i)<<endl;
}

}


Measured memory_bytes: 256
def com(n, k):
  P = [1]
  for i in range(1, n + 1):
    P.append(P[i - 1] * i)
  return P[n] / P[n - k] / P[k]


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

v.sort(reverse = True)
su = 0
for i in range(A):
  su += v[i]

ac = 0
t = v[A - 1]
k = 100
for i in range(N):
  if v[i] == t:
    ac += 1
    k = min(k, i)

print(su / A)
if k == 0:
  ans = 0
  for i in range(A, min(B, ac) + 1):
    ans += com(ac, i)
  print(int(ans))
else:
  print(int(com(ac, A - k)))

Measured memory_bytes: 3188
#include <iostream>
#include <math.h>
#include <sstream>
#include <iomanip>

using namespace std;

int main(){
	int N;
	cin >> N;
	
	if(N < 1000)
		cout << "ABC" << endl;
	else
		cout << "ABD" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;



int main(){
  ll n;
  cin >> n;
  ll ans = (n-1) * n/2;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int s;cin>>s;
  int a=s,ans=1;
  int h[1000000]={};
  while(h[a]==0){
    h[a]=1;
    if(a%2!=0){
      a=a*3+1;
    }else{
      a=a/2;
    }
    ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 4096
def main():
  x,y,z,k=map(int,input().split())
  one=[-int(i) for i in input().split()]
  two=[-int(i) for i in input().split()]
  three=[-int(i) for i in input().split()]
  one.sort()
  two.sort()
  three.sort()
  inf=10**11
  one.append(inf)
  two.append(inf)
  three.append(inf)
  
  import heapq 
  #print(one,two,three)
  q=[[one[0]+two[0]+three[0],0,0,0],[inf]]
  heapq.heapify(q)
  for i in range(k):
    m=heapq.heappop(q)
    while q[0]==m:
      m=heapq.heappop(q)
    print(-m[0])
    i,j,k=m[1],m[2],m[3]
    heapq.heappush(q,[one[i+1]+two[j]+three[k],i+1,j,k])
    heapq.heappush(q,[one[i]+two[j+1]+three[k],i,j+1,k])
    heapq.heappush(q,[one[i]+two[j]+three[k+1],i,j,k+1])

if __name__=='__main__':
  main()

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

const int INF = 1e9 +5;

int main()
{
 int n,k;
 cin>>n;
    cin>>k;
    int h[n], dp[n];
    for(int i=0;i<n;i++) {
        cin>>h[i];
        dp[i] = INF;
    }
    dp[0]= 0;
    for(int i=0;i<n;i++){
        for(int j=i+1; j<=(i+k);j++) {
            if(j<n){
            dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j])  );
            }
        }
   
    }
    cout<<  dp[n-1];
                    return 0;
                      
 
}

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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;

lli n,k;
vll a;
lli ans = 0;
map<lli,lli> zip;

class bit {
private:
	vll* v;
	lli n;
public:
	bit (lli n) {
		this->v = new vll(n+1);
		this->n = n;
	}
	void add(lli i,lli val){
		for(;i <= n;i += i&-i) this->v->at(i) += val;
	}
	lli sum(lli i){
		lli ret = 0;
		for(;i > 0;i -= i&-i) ret += this->v->at(i);
		return ret;
	}
};

int main(){
	cin >> n >> k;
	a = vll(n+1);
	for(lli i = 1;i <= n;i++) cin >> a[i];
	for(lli i = 1;i <= n;i++) a[i] -= k;
	for(lli i = 0;i < n;i++) a[i+1] += a[i];
	// for(lli i = 0;i <= n;i++){
	// 	for(lli j = i+1;j <= n;j++){
	// 		if(a[j] >= a[i]) ans++;
	// 	}
	// }
	for(lli i = 0;i <= n;i++) zip[a[i]] = 0;
	lli i = 1;
	for(auto itr = zip.begin();itr != zip.end();itr++){
		itr->second = i;
		i++;
	}
	bit b = bit(n+1);
	for(lli i = n;i >= 0;i--){
		ans += b.sum(n+1)-b.sum(zip[a[i]]-1);
		b.add(zip[a[i]],1);
	}
	cout << ans << endl;
	return 0;

}


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

int main()
{
    int H,A;
    cin >> H >> A;

    if( H%A == 0 ) cout << H/A << endl;
    else cout << H/A+1 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
#include<stack>
using namespace std;
#define PI 3.14159265358979
typedef  long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#include<set>
int main(void)
{
  int x;
  cin>>x;

  if(x<600) cout<<8<<endl;
  else if(x<800) cout<<7<<endl;
  else if(x<1000) cout<<6<<endl;
  else if(x<1200) cout<<5<<endl;
  else if(x<1400) cout<<4<<endl;
  else if(x<1600) cout<<3<<endl;
  else if(x<1800) cout<<2<<endl;
  else cout<<1<<endl;
}

Measured memory_bytes: 3164
L, R = gets.split.map(&:to_i)

ans = 2019

L.upto(R-1) do |i|
  (i+1).upto(R) do |j|
    mod = (i * j) % 2019
    if mod == 0
      puts 0
      exit
    end

    ans = mod if mod < ans
  end
end

puts ans


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

int main(int argc, const char * argv[]) {
    // insert code here...
    int a, b;
    cin >> a >> b;
    
    if (a * b % 2 == 0) cout << "Even" << endl;
    else cout << "Odd" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

 

using namespace std;

 

int main()
{
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r>=0 && y-r>=0 && x+r<=w && y+r<=h)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
#include <sstream>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define ios     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll mod=1000000007;
ll INF=1e18;
ll gcd (ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll fastexp(ll x ,ll n)
{
    ll result =1;
    while(n>0)
    {
        if(n%2==1)
            result*=x;
        x*=x;
        n=n/2;
    }
    return result;
}

ll modularExp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%mod;
        x=((x%mod)*(x%mod))%mod;
        n=n/2;
    }
    return (result)%mod;
}
bool isPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
bool mycomp(pll &a,pll &b)
{
    if(a.F!=b.F)
        return a.F < b.F;
    else
        return a.S < b.S;
}
map<ll,ll> mp;
vector<ll> pri(1000005,0);
void seive()
{
     ll i,j;
     for(i=2;i*i<=1000000;i++)
     {
          if(pri[i]==0)
          {
               for(j=i*i;j<=1000000;j+=i)
               {
                    if(pri[j]==0)
                         pri[j]=i;
               }
          }
     }
     for(i=2;i<=1000000;i++)
     {
          if(pri[i]==0)
               pri[i]=i;
          
     }
     
}
void solve()
{
     ll n;
     cin>>n;
     ll g=0;
     ll i;
     seive();
     vector<ll> v(n+1);
     for(i=1;i<=n;i++)
     {
          cin>>v[i];
          g=gcd(g,v[i]);
     }
     if(g!=1)
     {
          cout<<"not coprime";
          return;
     }
     bool f =true;
     for(i=1;i<=n;i++)
     {
          int x =v[i];
          while(x!=1)
          {
               ll y = pri[x];
               if(mp.find(y)!=mp.end())
               {
                    cout<<"setwise coprime";
                    return;
               }
               mp[y]=1;
               while(x%y==0)
                    x/=y;
          }
     }
     cout<<"pairwise coprime";
     
}

     
     


int main()
{
    ios;
    ll t;
//    cin>>t;
     t=1;
     while(t--)
     {
          solve();
     }
}

Measured memory_bytes: 18780
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;   //合計金額
  
  //入力
  cin >> N;
  
  bool split = false;  //割り切れるか（false: 割り切れない、true:割り切れる）
  int q;  //あまり
 
  //7ドルで買う最大枚数
  int num7 = N / 7;
  
  //7ドルの枚数が0~num7の各場合において、残りが4で割り切れるか検証
  for (int i = 0; i <= num7; i++){
    q = (N - i * 7) % 4;
    if (q == 0){
      split = true;
    }
  }
  
  //出力
  if (split){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
input()
a=list(map(int,input().split()))
b=0
for i in range(1,len(a)-1):
  b+=a[i-1]<a[i] and a[i]<a[i+1]
  b+=a[i-1]>a[i] and a[i]>a[i+1]
print(b)

Measured memory_bytes: 2940
#include <stdio.h>
#define N 100
#define INF 100000000

int min(int,int);

int main(){
  int n,i,p[N+1],m[N+1][N+1],l,j,k;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d %d",&p[i-1],&p[i]);
  }
  for(i=1;i<=n;i++){
    m[i][i]=0;
  }
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      m[i][j]=INF;
      for(k=i;k<=j-1;k++){
	m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
      }
    }
  }
  printf("%d\n",m[1][n]);
  return 0;
}

int min(int a,int b){
  if(a<b){
    return a;
  }
  else{
    return b;
  }
}



Measured memory_bytes: 2144
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            solve(in);
        }
    }

    private static void solve(Scanner in) {
        long N = in.nextLong(), M = in.nextLong();
        long ans = 0;
        if (N >= M / 2) {
            ans = M / 2;
        } else {
            ans = N;
            long rem = M - N * 2;
            ans += (rem / 4);
        }
        System.out.println(ans);
    }
}

class Scanner implements Closeable {
    private final InputStream stream;
    private final byte[] buf = new byte[1024];
    private int cur;
    private int num;

    Scanner(InputStream stream) {
        this.stream = stream;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    int nextInt() {
        return (int) nextLong();
    }

    long nextLong() {
        int c = read();
        while (isdel(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long l = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            l *= 10;
            l += c - '0';
            c = read();
        } while (!isdel(c));
        return l * sgn;
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String next() {
        int c = read();
        while (isdel(c))
            c = read();
        StringBuilder s = new StringBuilder();
        do {
            s.appendCodePoint(c);
            c = read();
        } while (!isdel(c));
        return s.toString();
    }

    private int read() {
        if (num == -1)
            throw new InputMismatchException();
        if (cur >= num) {
            cur = 0;
            try {
                num = stream.read(buf);
            } catch (Exception e) {
                throw new InputMismatchException();
            }
            if (num <= 0)
                return -1;
        }
        return buf[cur++];
    }

    private boolean isdel(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    @Override
    public void close() {
        try {
            stream.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

Measured memory_bytes: 23124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char a= sc.next().toCharArray()[0];
		char b= sc.next().toCharArray()[0];
		if (a>b) {
			System.out.println('>');
		} else if (a==b) {
			System.out.println('=');
		} else {
			System.out.println('<');
		}
	}
}

Measured memory_bytes: 21844
// failed to generate code

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


double dp[301][301][301];
int N;

double dfs(int c1,int c2,int c3){
    if( c1 == 0 && c2 == 0 && c3 == 0) return 0.0;
    if( dp[c1][c2][c3] != -1 ) return dp[c1][c2][c3];
    double ans = 0;

    double p1 = 1. * c1 / N;
    double p2 = 1. * c2 / N;
    double p3 = 1. * c3 / N;
    double p0 = 1. * (N - c1 - c2 - c3) / N;

    if(p1) ans += p1 * (dfs(c1-1, c2, c3) + 1);
    if(p2) ans += p2 * (dfs(c1+1, c2-1, c3) + 1);
    if(p3) ans += p3 * (dfs(c1, c2+1, c3-1) + 1);
    // ans += p0 * (dfs(c1, c2, c3) + 1);
    ans += p0;

    ans /= (1-p0);

    return dp[c1][c2][c3] = ans;
}

int main(){
    for(int i = 0 ; i < 301 ; i++)
        for(int j = 0 ; j < 301 ; j++)
            for(int k = 0 ; k < 301 ; k++)
                dp[i][j][k] = -1;
    ios::sync_with_stdio(false);
    cin >> N;
    int c[3] = {};
    for(int i = 0 ; i < N ; i++) {
        int x;
        cin >> x;
        c[x-1]++;
    }


    printf("%.10lf\n", dfs(c[0], c[1], c[2]));


}


Measured memory_bytes: 213376
/**
 * @author torith
 * @date 2018-10-27
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> a,b;
    for (int i = 0; i < N; ++i) {
        int t; cin >> t;
        if(i % 2 == 0) a.push_back(t);
        else b.push_back(t);
    }

    if(N % 2 == 0){
        // bを先に出していく
        for (int i = 0; i < b.size(); ++i) {
            cout << *(b.end()-1-i)  << " ";
        }
        for (auto &i: a){
            cout << i << " ";
        }
    }else{
        for (int i = 0; i < a.size(); ++i) {
            cout << *(a.end()-1-i)  << " ";
        }
        for (auto &i: b){
            cout << i << " ";
        }
    }
    return 0;
}



Measured memory_bytes: 3188
from itertools import product
n,m=map(int,input().split())
a=[]
for i in range(m):
     a.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
x=[0,1]
x=list(product(x,repeat=n))
c=0
for k in x:
     f=True
     for i in range(m):
          a_=a[i]
          cnt=0
          for j in a_:
               cnt+=k[j-1]
          cnt%=2
          if cnt!=p[i]:
               f=False
               break
     c+=f
print(c)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
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;
}
int main(){
    string S;
    cin>>S;
    ll N=S.size();
    ll mark=0;
    rep(i,N){
        mark=(mark+(S.at(i)-'0'))%9;
    }
    if(mark%9==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, a[100005], v, u, t;
bool out;
vector<int> G[100005];
ll dfs(int u, int p){
	if(G[u].size() == 1) return a[u];
	ll mxv = 0, ac = 0, ret;
	for(int nx: G[u]) if(nx != p){
		ll tmp = dfs(nx,u);
		ac += tmp;
		mxv = max(mxv, tmp);
	}
	ret = a[u] * 2 - ac;
	mxv = max(mxv, ret);
	if(ret < 0 || a[u] < mxv) out = true;
	return ret;
}
int main(){
	scanf("%d", &n);
	rep(i,n) scanf("%d", a+i);
	rep(i,n-1){
		scanf("%d%d", &v, &u);
		v--; u--;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	if(n == 2){
		puts(a[0] == a[1] ? "YES" : "NO");
		return 0;
	}
	for(; G[t].size() == 1; t++);
	if(dfs(t,t) > 0 || out) puts("NO");
	else puts("YES");
}

Measured memory_bytes: 12800
def fibonacci(n, memo=None):
    if memo==None:
        memo = [None]*n
    if n<=1:
        return 1 
    else:
        if memo[n-2]==None:
            memo[n-2] = fibonacci(n-2, memo)
        if memo[n-1]==None:
            memo[n-1] = fibonacci(n-1, memo)
    return memo[n-1] + memo[n-2]

n = int(input())
print(fibonacci(n))

Measured memory_bytes: 7684
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;
#pragma endregion

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if ((a == b && b != c) || (a == c && a != b) || (a != b && b == c)) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  const int max = 1000000;
  vector<int> result;
  bool nums[max];
  for (int i = 2; i < max; i++)
    nums[i] = true;
  for (int i = 2; i < max; i++) {
    if (!nums[i])
      continue;
    else if (i * i > max)
      break;
    for (int j = i+1; j < max; j++) {
      if (!nums[j])
        continue;
      else if (j % i == 0)
        nums[j] = false;
    }
  }

  while (cin >> n) {
    int piyo = 0;
    for (int i = 2; i <= n; i++)
      if (nums[i])
        piyo++;
    result.push_back(piyo);
  }

  for (int i = 0; i < result.size(); i++)
    cout << result[i] << endl;
  return 0;
}

Measured memory_bytes: 2188
#include<stdio.h>
#include<math.h>

int main(void)
{
  int w,h;
  char s[60][30];
  int i,j,m,n,c;
  int dp[60][30][2];
  int tmp1,tmp2,min;

  while(1){
    scanf("%d %d ",&w,&h);
    if(w==0 && h==0)break;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	scanf("%c ",&s[i][j]);
      }
    }

    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	dp[i][j][0] = -1;
	dp[i][j][1] = -1;
      }
    }

    for(i=0;i<w;i++){
      if(s[h-1][i] == 'S'){
        dp[h-1][i][0] = 0;
        dp[h-1][i][1] = 0;
      }
    }

    
    while(1){
      c=0;
      for(i=0;i<h;i++){
	for(j=0;j<w;j++){ 
	  if(dp[i][j][0] >= 0){
	    for(m=-2;m<=2;m++){
	      for(n=1;n<=3;n++){
		if(i+m>=0 && i+m<h && j+n<w && fabs(m)+n<=3 && s[i+m][j+n]!='X'){
		  tmp1 = dp[i+m][j+n][1];
		  if(s[i+m][j+n] == 'S' || s[i+m][j+n] == 'T'){
		    tmp2 = dp[i][j][0];
		  }else{
		    tmp2 = dp[i][j][0] + s[i+m][j+n] - '0';
		  }
		  if(tmp1 < 0 || tmp1 > tmp2){
		    dp[i+m][j+n][1] = tmp2;
		    c++;
		  }
		}
	      }
	    }
	  }
	  if(dp[i][j][1] >= 0){
	    for(m=-2;m<=2;m++){
	      for(n=1;n<=3;n++){
		if(i+m>=0 && i+m<h && j-n>=0 && fabs(m)+n<=3 && s[i+m][j-n]!='X'){
		  tmp1 = dp[i+m][j-n][0];
		  if(s[i+m][j-n] == 'S' || s[i+m][j-n] == 'T'){
		    tmp2 = dp[i][j][1];
		  }else{
		    tmp2 = dp[i][j][1] + (int)(s[i+m][j-n] - '0');
		  }
		  if(tmp1 < 0 || tmp1 > tmp2){
		    dp[i+m][j-n][0] = tmp2;
		    c++;
	          }
		}
	      }
	    }
	  }
	}
      }
      if(c==0)break;
    }

    min = -1;
    for(i=0;i<w;i++){
      if(s[0][i] == 'T'){
	 for(j=0;j<2;j++){
           if(min < 0 || (dp[0][i][j] > 0 && min > dp[0][i][j]))min = dp[0][i][j];
	}
      }
    }

    printf("%d\n",min);
    
  }
  return 0;
}

Measured memory_bytes: 428
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VP v(n);
    REP(i,0,n) cin >> v[i].first >> v[i].second;
    sort(all(v), [](auto &l, auto &r) {return l.first + l.second > r.first + r.second;});
    LL ans = 0;
    REP(i,0,n) {
        if (i % 2 == 0) ans += v[i].first;
        else ans -= v[i].second;
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;

ll dp[110][500][110];

int main() {
	int i, j, k, n, W; cin >> n >> W;
	vector <ll> w(n), v(n);
	for (i = 0; i < n; i++)cin >> w[i] >> v[i];
	int w1 = w[0];

	for (i = 0; i < n; i++)w[i] -= w1;

	for (i = 0; i < 110; i++) {
		for (j = 0; j < 500; j++) {
			for (k = 0; k < 110; k++) {
				dp[i][j][k] = -1;
			}
		}
	}
	dp[0][0][0] = 0;//初期化をちゃんとしよう。

	for (i = 0; i < n; i++) {
		for (j = 0; j < 500; j++) {
			for (k = 0; k <= i; k++) {
				if (dp[i][j][k] < 0)continue;
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
				if ((ll)(j + w[i] + w1*(k+1) <= W)) {
					dp[i + 1][j + w[i]][k+1] = max(dp[i + 1][j + w[i]][k+1], dp[i][j][k] + v[i]);
				}
			}
		}
	}
	
	ll ans = 0;
	for (i = 0; i < 500; i++) {
		for (j = 0; j <= n; j++) {
			if (dp[n][i][j] < 0)continue;
			if (i + w1 * j <= W)ans = max(ans, dp[n][i][j]);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 47488
#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<int,int> 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; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,1,-1,1,-1,-1,0};
int dy[]={0,1,1,-1,-1,1,0,-1};




int main(){
    int n;cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    vector<int> mi(n);
    int m = INF;
    for (int i = 0; i < n; i++) {
        m = min(m,p[i]);
        mi[i] = m;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if(mi[i] >= p[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        HashMap<String,String> map = new HashMap<>();
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            String k = sc.next();
            if(!map.containsKey(k)){
                map.put(k, "a");
            }
            
        }
        System.out.println(map.size());

    }
}

Measured memory_bytes: 78124
n = int(input())
l = [int(x) for x in input().split()]

order = 0
subs = []
tmp = []

prev = 0
d = []
t = [l[0]]
for x in range(len(l)-1):
  a,b = l[x],l[x+1]
  c = a-b
  # print(a,b,c, prev)
  if c == 0:
    t.append(b)
  elif prev == 0:
    t.append(b)
    prev = c
  elif (c < 0  and prev < 0) or (c > 0 and prev > 0):
    t.append(b)
  else:
    prev = 0
    d.append(t)
    t = [b]
d.append(t)

print(len(d))


Measured memory_bytes: 14252
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 (ll)1 << 60
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, m, ans = INF64, s[20], t[20];
int main() {
	cin >> n >> m;
	REP(i, n)cin >> s[i] >> t[i];
	REP(i, 1 << n) {
		ll now = 0, nn = 0;
		vector<ll> v;
		REP(j, n) {
			if (i & (1 << j)) {
				now += s[j] * (j + 1) * 100 + t[j];
				nn += s[j];
			}
			else {
				REP(k, s[j])v.push_back((j + 1) * 100);
			}
		}
		sort(ALL(v), greater<ll>());
		if (now >= m)ans = min(ans, nn);
		REP(j, v.size()) {
			now += v[j];
			nn++;
			if (now >= m)ans = min(ans, nn);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    A=input()
    ac=list(Counter(A).values())
    len_a=len(A)
    ans=len_a*(len_a-1)//2
    for acc in ac:
        ans-=acc*(acc-1)//2
    print(ans+1)

if __name__=='__main__':
    main()

Measured memory_bytes: 3752
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s,t;
  cin >> s;
  cin >> t;
  int p=s.size();
  int q=t.size();
  int dp[3010][3010];

  /*for(int i=0;i<=p;i++){
    for(int j=0;j<=q;j++){
      dp[i][j]=0;
    }
  }*/

  for(int i=0;i<p;i++){
    for(int j=0;j<q;j++){
      if(s[i]==t[j]){
        dp[i+1][j+1]=dp[i][j]+1;
      }else{
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
      }
    }
  }
  vector<char> ans;
  while(p>0 && q>0){
    if(s[p-1]==t[q-1]){
      ans.push_back(s[p-1]);
      p--,q--;
    }else{
      if(dp[p-1][q]>dp[p][q-1]){
        p--;
      }else{
        q--;
      }
    }
  }
  reverse(ans.begin(),ans.end());
  for(int i=0;i<ans.size();i++){
    cout << ans[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1LL<<55LL; 
int cnt;
void merge(int *A,int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int L[n1+1],R[n2+1];
  for(int i=0;i<n1;i++) L[i]=A[left+i];
  for(int i=0;i<n2;i++) R[i]=A[mid +i];
  L[n1]=INF;
  R[n2]=INF;
  int i=0,j=0;
  for(int k=left;k<right;k++){
    cnt++;
    if(L[i]<=R[j]) A[k]=L[i++];
    else A[k]=R[j++];
  }
}
void mergeSort(int *A,int left,int right){
  if(left+1<right){
    int mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n;
  cin>>n;
  int S[n];
  for(int i=0;i<n;i++) cin>>S[i];
  cnt=0;
  mergeSort(S,0,n);
  for(int i=0;i<n;i++) cout<<S[i]<<" \n"[i==n-1];
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 10876
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b = IL()

ans = 1
while ans < 10000:
  if int(ans*0.08) == a and int(ans*0.10) == b:
    print(ans)
    exit()
  ans += 1
print(-1)


Measured memory_bytes: 38896
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    vector<int> arr(2, 0);
    for(auto& val: arr) {
        cin >> val;
        if (val == 1)
            val += 100;
    }
    if (arr[0] > arr[1])
        cout << "Alice" << endl;
    else if (arr[0] < arr[1])
        cout << "Bob" << endl;
    else
        cout << "Draw" << endl;
    return 0;
}


Measured memory_bytes: 3604