akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();


int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> arr(n, 0);
    for(ll& val: arr)
        cin >> val;
    ll ans = 0;
    ll acc = 0, acc2 = 0;
    vector<ll> dp(n+1, 0);
    vector<ll> exclude(n+1, 0);
    for(int i = 0; i < n; i++) {
        acc += arr[i];
        dp[i+1] = acc;
        acc2 += max(0LL, arr[i]);
        exclude[i+1] = acc2;
    }
    for(int i = k; i < dp.size(); i++) {
        ll exc = acc2 - (exclude[i]-exclude[i-k]);
        ans = max(ans, exc+max(dp[i]-dp[i-k], 0LL));
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 2560
#include <iostream>
 
using namespace std;
 
int main(){
    int L=0,N,A,B,C,D;
    while(cin>>N){L=0;
    for(A=0;A<10;A++){
        for(B=0;B<10;B++){
            for(C=0;C<10;C++){
                for(D=0;D<10;D++){ 
                    if(A+B+C+D==N){L++;};
                };};};};
 
    cout<<L<<endl;};
    cin>>L;
        return 0;
 
}

Measured memory_bytes: 1156
H, W = map(int, raw_input().split())
board = []
for i in range(0, H):
	s = raw_input()
	lst = []
	for j in range(0, W):
		lst.append(s[j])
	board.append(lst)
down = []
for i in range(0, W):
	down.append(False)
for i in range(0, H):
	for j in range(0, W):
		if board[i][j] == '#': down[j] = True
for i in range(0, H):
	if '#' in board[i]:
		outs = ''
		for j in range(0, W):
			if down[j]: outs = outs + board[i][j]
		print outs

Measured memory_bytes: 32796
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;


int main(){
    fast_io

    int n;
    cin>>n;
    cout<<n/3<<endl;
    return 0;
}


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

signed main() {
	int k; cin >> k;
	int o = (k + 1) / 2, e = k / 2;
	cout << o*e << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
#include <utility>
// #include <numeric>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector<vector<ll>> vvint;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define LLONG_MAX 9223372036854775807
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())



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

ll X,Y,Z,K;
ll pmax = 30000000000;
vint A,B,C;




// int binary_search(int key){
//  //isOKを満たす要素のうち最小のインデックスを返す。（要ソート）
//   int left = -1;
//   int right = N;
//
//   while(right - left > 1){
//     int mid = left + (right - left)/2;
//
//     if(isOK(mid, key)) right=mid;
//     else left=mid;
//   }
//
//   return right;
// }

// ll gcd(ll m, ll n){
//   if(m<n) swap(m,n);
//   if(n==0) return m;
//   return gcd(n, m%n);
// }



int main() {



  ll N;
  cin>>N;
  vint a(N,0);

  ll cnt = 0;
  ll ans = 0;
  ll minabsval = LLONG_MAX;

  rep(i,N){
    cin>>a[i];
    ll absval = abs(a[i]);
    ans += absval;
    minabsval = min(minabsval, absval);
    if(a[i]<0) cnt++;
  }

  if(cnt%2==1){
    ans -= (2*minabsval);
  }

  cout << ans << endl;


}

















//


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
string s;

int main(){
	cin >> s; int a=0,b=0;
	REP(i,0,s.size()) if(s[i]=='A'){a=i; break;}
	RREP(i,s.size()-1,0) if(s[i]=='Z'){b=i+1; break;}
	cout << b-a << endl;
	return 0;
}


Measured memory_bytes: 640
fun main(args:Array<String>?): Unit {
    val n = readLine()!!.trim().toInt()
    val (a, b) = readLine()!!.trim().split(' ').map(String::toInt)
    val (c, d) = readLine()!!.trim().split(' ').map(String::toInt)

    println(
            (1 .. n).map{w -> Section((a - 1) % w, (a - 1) / w).manhattanDistance(Section((b - 1) % w, (b - 1) / w)) + Section((c - 1) % w, (c - 1) / w).manhattanDistance(Section((d - 1) % w, (d - 1) / w))}.min()!!
    )
}
data class Section(val x: Int, val y: Int) {
    fun manhattanDistance(from: Section): Int = Math.abs(x - from.x) + Math.abs(y - from.y)
}


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

using namespace std;

const int N = 2e5+5;

const int mod = 1e9+7;

string s;

int main(){
    cin >> s;
    for(int i = 0; i+1 < s.size(); i++){
        if(s[i] == s[i + 1]){
            cout << i+1 << " " << i + 2 << "\n";
            return 0;
        }
    }
    for(int i = 0; i+2 < s.size(); i++){
        if(s[i] == s[i + 2]){
            cout << i+1 << " " << i + 3 << "\n";
            return 0;
        }
    }
    cout << -1 << " " << -1 << "\n";
}

Measured memory_bytes: 3728
#include <iostream>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c;
    int size = 3;
    int* check = new int[size];
    check[0]=5; check[1]=7; check[2]=5;

    cin >> a >> b >> c;

    for (int i=0; i<size;i++){
        if (check[i]==a){
            check[i]=0;
            break;
        } 
    }
    for (int i=0; i<size;i++){
        if (check[i]==b){
            check[i]=0;
            break;
        } 
    }
    for (int i=0; i<size;i++){
        if (check[i]==c){
            check[i]=0;
            break;
        } 
    }
    int sum = 0;
    for (int i=0; i<size;i++){
        sum+=check[i] ;
    }
    if (sum == 0){
        cout << "YES" <<"\n";
    }else{
        cout << "NO" <<"\n";
    }
}

Measured memory_bytes: 256
n, m = map(int, input().split())
A = []
B = []
C = []
D = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(m):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

for i in range(n):
    dis = []
    for j in range(m):
        dis.append(abs(A[i] - C[j]) + abs(B[i] - D[j]))
    mi = min(dis)
    for j in range(m):
        if dis[j] == mi:
            print(j + 1)
            break


Measured memory_bytes: 69036
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  long long int arr[n], max = 1e18, x = 1, y = 0, zero = 0;
  
  for (int i = 0; i < n; i++) {
    scanf("%lld", &arr[i]);
    y = (arr[i] > max) ? 1 : y;
    x *= arr[i];
    (arr[i]) ? max /= arr[i] : zero = 1;
  }

  (zero) ? puts("0") : ((y) ? puts("-1") : printf("%lld\n", x));
  return 0;
}

Measured memory_bytes: 4004
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<bitset>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	int N,K;
	scan(N>>K);
	int ans=0;
	while(N){
		N/=K;
		ans++;
	}
	prin(ans);
	return 0;
}


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

using namespace std;

template <typename T> void read(T& x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int H, W, h, w;

int main()
{
	cin >> H >> W;
	cin >> h >> w;
	cout<<(H-h)*(W-w)<<endl;
	return 0;
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int cnt = 1;
  char now;
  //cout << cnt;
  rep(i,s.size()){
      if (i == 0)now = s[i];
      else{
          if (s[i] != now)cnt += 1;
          now = s[i];
      }
  }
  cout << cnt;
}

Measured memory_bytes: 3772
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

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

  int balls[n];
  bool pro[n];
  for(int i=0; i<n; i++){
    balls[i] = 1;
    pro[i] = false;
  }

  pro[0] = true;
  for(int i=0; i<m; i++){
    int x, y; cin >> x >> y;
    balls[x-1]--; balls[y-1]++;

    if(pro[x-1]) pro[y-1] = true;

    if(balls[x-1] == 0) pro[x-1] = false;
  }

  int ans = 0;
  for(int i=0; i<n; i++){
    if(balls[i] && pro[i]){
      ans++;
    }
  }

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


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

int main() {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    
    int ans = 0;
    for(int i = 0; i <= a; i++) {
        for(int j = 0; j <= b; j++) {
            for(int h = 0; h <= c; h++) {
                if(500 * i + 100 * j + 50 * h == x) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    int64_t s = 0, t = 0;
    rep(i, m)
    {
        int64_t d, c;
        cin >> d >> c;
        s += d * c;
        t += c;
    }

    int64_t result = t - 1 + (s - 1) / 9;
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 256
// eddy1021
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long ll;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<LD,LD> Pt;
typedef tuple<int,int,int> tiii;
typedef tuple<LL,LL,LL> tlll;
#define mod9 1000000009ll
#define mod7 1000000007ll
#define INF  1023456789ll
#define INF16 10000000000000000ll
#define FI first
#define SE second
#define X FI
#define Y SE
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
int __ = 1 , _cs;
/*********default*********/
#define N 202020
void build(){

}
int w , h;
vector< pair< int , int > > vv;
void init(){
  w = getint();
  h = getint();
  for( int i = 0 ; i < w ; i ++ ){
    int pi = getint();
    vv.push_back( { pi , 0 } );
  }
  for( int i = 0 ; i < h ; i ++ ){
    int qi = getint();
    vv.push_back( { qi , 1 } );
  }
}
void solve(){
  sort( vv.begin() , vv.end() );
  LL ans = 0;
  w ++ , h ++;
  for( auto i : vv ){
    LL cst = i.first;
    int who = i.second;
    if( who == 0 ){
      ans += (LL)h * cst;
      w --;
    }else{
      ans += (LL)w * cst;
      h --;
    }
  }
  cout << ans << endl;
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int div_roundup(int x, int y)
{
	return (x + y - 1) / y;
}

int simulate(int D, int G, const vector<int> &p, const vector<int> &c, const vector<int> &x)
{
	int num = 0;

	for (auto i : x) {
		int t = div_roundup(G, 100 * (i + 1));
		if (t < p[i]) {
			num += t;
			G -= 100 * (i + 1) * p[i];
		}
		else {
			num += p[i];
			G -= 100 * (i + 1) * p[i] + c[i];
		}
		if (G <= 0) {
			break;
		}
	}
	
	return num;
}

int main()
{
	int D, G;
	cin >> D >> G;
	vector<int> p(D), c(D), x(D);
	for (int i = 0; i < D; ++i) {
		cin >> p[i] >> c[i];
		x[i] = i;
	}

	int ans = 1 << 30;
	do {
		int result = simulate(D, G, p, c, x);
		ans = min(ans, result);
	} while (next_permutation(x.begin(), x.end()));

	cout << ans << endl;
}


Measured memory_bytes: 384
a, b, k = map(int, input().split())

for i in range(1, k + 1):
    if i % 2 == 1:
        if a % 2 == 1:
            a -= 1
        a /= 2
        b += a

    elif i % 2 == 0:
        if b % 2 == 1:
            b -= 1
        b /= 2
        a += b
print(int(a), int(b))

Measured memory_bytes: 3060
import java.util.*;
import java.lang.*;

public class Main {
	static Graph graph;
	static int[] c;
	static int[] value;
	static int index;
	static boolean[] visited;
	static long sum;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		graph = new Graph(n);
		for (int i = 0; i < n - 1; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			graph.addChild(a, b);
			graph.addChild(b, a);
		}
		c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
		}
		Arrays.sort(c);
		value = new int[n];
		value[0] = c[n - 1];
		index = n - 2;
		visited = new boolean[n];
		sum = 0;
		dfs(0);
		System.out.println(sum);
		for (int i = 0; i < n - 1; i++) {
			System.out.print(value[i] + " ");
		}
		System.out.println(value[n - 1]);
	}
	static void dfs(int node) {
		visited[node] = true;
		int size = graph.child[node].size();
		for (int i = 0; i < size; i++) {
			int child = graph.child[node].get(i);
			if (!visited[child]) {
				value[child] = c[index];
				sum += c[index];
				index--;
				dfs(child);
			}
		}
	}
}

class Graph {
	ArrayList<Integer>[] child;

	Graph(int n) {
		child = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			child[i] = new ArrayList<>();
		}
	}

	void addChild(int node, int v) {
		child[node].add(v);
	}
}

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

int main() {
    int N;
    cin >> N;
    vector< vector<int> > g(N, vector<int>(N, -1));
    // g[i][j] := i人目の証言におけるj人目の真偽
    int a;
    int x, y;
    for(int i = 0; i < N; i++){
        cin >> a;
        for(int j = 0; j < a; j++){
            cin >> x >> y;
            g[i][x-1] = y;
        }
    }

    int ans = 0;
    for(int bit = 0; bit < (1<<N); bit++){
        vector<int> d(N, 0);
        // bitをvectorに変換 d[i] := i人目が親切かどうか
        for(int i = 0; i < N; i++){
            if(bit & (1 << i)){
                d[i] = 1;
            }
        }

        bool flag = true; // 矛盾が起きているかどうか
        for(int i = 0; i < N; i++){
            if(d[i] == 1){
                for(int j = 0; j < N; j++){
                    if(g[i][j] == -1){
                        continue;
                    }
                    if(g[i][j] != d[j]){
                        flag = false;
                        break;
                    }
                }
            }
        }

        if(flag == true){
            ans = max(ans, __builtin_popcount(bit));
        }
    }

    cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int H,W,i,j,a;
	for(;;){
		cin>>H>>W;
		if(H==0&&W==0){
			break;
		}
		for(i=0;i<H;i++){
			for(j=0;j<W;j++){
				a=i+j;
				if(a%2==1){
					cout<<".";
				}
				if(a%2==0){
					cout<<"#";
				}
			}cout<<endl;
		}cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 3080
fn main(){
    let line : Vec<_> = getline().trim().split(' ').map(|e| e.parse::<i64>().unwrap()).collect();
    let h = line[0];
    let w = line[1];
    
    let mut field : Vec<Vec<_>> = (0..h).map(|_| getline().trim().bytes().collect()).collect();
    
    let mut y_ng = Vec::with_capacity(h as usize);
    let mut x_ng = Vec::with_capacity(w as usize);
    
    for y in 0..h as usize{
        let mut flg = true;
        for x in 0..w as usize {
            flg &= field[y][x] == '.' as u8;
        }
        y_ng.push(flg);
    }
    for x in 0..w as usize {
        let mut flg = true;
        for y in 0..h as usize {
            flg &= field[y][x] == '.' as u8;
        }
        x_ng.push(flg);
    }
    
    for y in 0..h as usize{
        if (y_ng[y]) { continue; }
        for x in 0..w as usize {
            if (!x_ng[x]) {
                print!("{}", field[y][x] as char);
            }
        }
        println!("");
    }
}

fn getline() -> String{
    let mut __ret=String::new();
    std::io::stdin().read_line(&mut __ret).ok();
    return __ret;
}


Measured memory_bytes: 4352
from fractions import gcd
K = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)

print(ans)


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

using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > ii;
#define repi(i, a, b)    for(int i = a; i < b; i++)
#define repd(i, a, b)    for(int i = b-1; i >= a; i--)   
#define rep(i, n)        for(int i = 0; i < n; ++i)
#define ll               long long int
#define I                iterator
#define lf               long double
#define pb               push_back
#define pq               priority_queue
#define all(c)           (c).begin(), (c).end()




int main(){
    int a, b;
    cin >> a >> b;
    if(a >= 13){
        cout << b << endl;
    }else if(a >= 6){
        cout << b/2 << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(x) x.begin(),x.end()

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll i,ans=0;string S,T;cin>>S>>T;
  REP(i,S.size())if(S[i]!=T[i])ans++;
  cout<<ans<<endl;

  return 0;

}

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

Measured memory_bytes: 4848
def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(M)]
    for i in range(M):
        X[i].append(i)

    X.sort(key=lambda X:(X[0],X[1]))
    anslist = [[0,0] for _ in range(M)]
    tmp = 0
    count = 1
    for i in range(M):
        if tmp != X[i][0]:
            tmp = X[i][0]
            count = 1
            anslist[i][0] = "0"*(6-len(str(X[i][0])))+str(X[i][0])+"0"*(6-len(str(count)))+str(count)
            anslist[i][1] = X[i][2]
        else:
            count += 1
            anslist[i][0] = "0"*(6-len(str(X[i][0])))+str(X[i][0])+"0"*(6-len(str(count)))+str(count)
            anslist[i][1] = X[i][2]
            
    anslist.sort(key=lambda X:X[1])
    for i in range(M):
        print(anslist[i][0])

if __name__ == "__main__":
    main()

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

int main() {
    
    int s_len, t_len;
    cin >> s_len;
    int s[s_len] = {};
    
    for(int i = 0; i < s_len; i++) {
        cin >> s[i];
    }
    
    cin >> t_len; 
    int t[t_len] = {};
    
    for(int i = 0; i < t_len; i++) {
        cin >> t[i];
    }
    
    int count = 0; 
    bool found = false;
    for(int i = 0; i < t_len; i++) {
        for(int j = 0; j < s_len; j++) {
            if(t[i] == s[j]) {
                found = true;
            }
        }
        if(found) {
            count = count +1;
        }
        found = false;
    }
    
    cout << count << endl;
}


Measured memory_bytes: 3076
#include <iostream>
#include<algorithm>
using namespace std;
const int maxn = 100;
int a[maxn];
int b[maxn];
int c[maxn];
int d[maxn];
int n,m,q;
int tmp[maxn];//临时数组用来存储选出的数
int ans = -1;
int vis[maxn]={0};
void dfs(int k,int s )//从m个数里选n个数,注意这些数字可能想同
{


       if(k>n)
    {
         int sum = 0;
         //sort(tmp+1,tmp+n+1);
        // for(int i=1;i<=n;i++) cout<<tmp[i];
         //cout<<endl;
          for(int i=1;i<=q;i++)
         {
            if(tmp[b[i]]-tmp[a[i]]==c[i])
            {
                sum+=d[i];
            }
         }
         if(sum>ans) ans = sum;
        return ;
    }
    for(int i=s;i<=m;i++)
    {
        tmp[k] = i;
        dfs(k+1,i);
        tmp[k] = 0;
    }
}
int main()
{
   cin>>n>>m>>q;
   //cin>>n>>m;
    for(int i=1;i<=q;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    dfs(1,1);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define base 1000000007LL
#define ll long long
#define X first
#define Y second
#define pb push_back
#define Scan(a) scanf("%I64d", &a);
#define CLR(a) memset(a,0,sizeof(a))
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORE(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)

using namespace std;

typedef pair<int, int> II;
typedef vector<II> vi;

int w, h, n, l, r, u, d, a, x, y;

int main()
{
    ios::sync_with_stdio(0);
    //freopen("inp.txt", "r", stdin);
    cin >> w >> h >> n;
    l = 0;
    r = w;
    u = h;
    d = 0;
    FOR(i,1,n) {
        cin >> x >> y >> a;
        if (a == 1) l = max(l, x);
        else if (a == 2) r = min(r, x);
        else if (a == 3) d = max(d, y);
        else u = min(u, y);
    }
    int res = (r-l)*(u-d);
    if (r < l || u < d) res = 0;
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 2010
#define INF 2000000000000LL
#define LL long long
LL x,a[MAXN],ans;
LL dp[MAXN][MAXN];
int n;
int main()
{
	scanf("%d%lld",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	ans=INF;
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=dp[i-1][0]+a[i];
		LL mn=a[i];
		for(int j=1;j<n;j++)
		{
			int p=(i-j)<=0?(i-j+n):(i-j);
			mn=min(a[p],mn);
			dp[i][j]=min(dp[i][j-1],dp[i-1][j]+mn);
		}
	}
	for(int i=0;i<n;i++)
		ans=min(ans,dp[n][i]+i*x);
	printf("%lld\n",ans);
}

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

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

typedef long long ll;

using namespace std;

int a, b, c, d;

void solve() {
    scanf("%d %d %d %d", &a, &b, &c, &d);
    printf("%d\n", min(a, b) + min(c, d));
}

int main() {
    #ifdef BThero
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // BThero

    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 256
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))


Measured memory_bytes: 76828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

void solve(string S){
	if (S == "Sunny") cout << "Cloudy" << endl;
	if (S == "Cloudy") cout << "Rainy" << endl;
	if (S == "Rainy") cout << "Sunny" << endl;
}

int main(){	
	string S;
	cin >> S;
	solve(S);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;

int main() {
	
	cin.tie(0); cout.tie(0);
	ll a, b, c; cin >> a >> b >> c;
	ll t = c / a;
	ll s = 0;
	s += t * b;
	cout << s;
 	return 0;                         
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll h,w,n;
  cin >> h >> w >> n;
  ll sr,sc;
  cin >> sr >> sc;
  string s,t;
  cin >> s >> t;
  ll Rlim=w-sc,Llim=sc-1,Ulim=sr-1,Dlim=h-sr;
  ll r=0,l=0,u=0,d=0;
  rep(i,n){
    if(s[i]=='R'){
      r++;
    }
    else if(s[i]=='L'){
      l++;
    }
    else if(s[i]=='U'){
      u++;
    }
    else{
      d++;
    }
    if(r>Rlim||l>Llim||u>Ulim||d>Dlim){
      cout << "NO" << endl;
      return 0;
    }
    if(t[i]=='R'&&-l<Rlim)l--;
    if(t[i]=='L'&&-r<Llim)r--;
    if(t[i]=='U'&&-d<Ulim)d--;
    if(t[i]=='D'&&-u<Dlim)u--;
  }
  cout << "YES" << endl;
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int X,A;
    Scd2(X,A);

    printf ("%d\n", X < A ? 0 : 10 );

    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // R * x + G * y + B * z = N
  int R, G, B, N;
  cin >> R >> G >> B >> N;

  int ans = 0;
  for (int x = 0; x <= N; ++x) {
    for (int y = 0; y <= N; ++y) {
      int t = N - R * x - G * y;
      if (t >= 0 && t % B == 0)
        ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl '\n'
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define TOUPPER(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define TOLOWER(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define FILLZERO(s, n)                      \
    do {                                    \
        ostringstream os;                   \
        os << setw(n) << setfill('0') << s; \
        s = os.str();                       \
    } while (0);
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
#define INIT                               \
    std::cin.tie(nullptr);                 \
    std::ios_base::sync_with_stdio(false); \
    cout << std::fixed << std::setprecision(10);

template <typename T>
vector<T> make_vec(size_t a, T n) { return vector<T>(a, n); }
template <typename T, typename... Ts>
auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); }
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
T intceil(T a, T b) {
    return (a + (b - 1)) / b;
}

signed main() {
    INIT;
    cin >> S;
    int g = 1, p = 0;
    int w = 0, l = 0;
    REPS(i, S.size() - 1) {
        if (g > p) {
            if (S[i] == 'g')
                w++;
            p++;
        } else {
            if (S[i] == 'p') {
                l++;
            }
            g++;
        }
        dump(w, l);
    }
    cout << w - l << endl;
}

Measured memory_bytes: 3744
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

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

int main() {
	int n, k;
	cin >> n >> k;
	double p = 0;
	for (int i = 1; i <= n; i++) { //サイコロの出目がnのとき勝つ確率に注目
		double now;
		//何回表が出ればよいか
		int num = 0;
		int x = i;
		while (x < k) {
			x *= 2;
			num++;
		}
		ll  power = 1;
		rep(j, num) {
			power *= 2;
		}
		now = (double) 1 / (n * power);
		p += now;
	}
	cout << fixed << setprecision(10);
	cout << p << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << (x) << endl

// score, a, b, id
using Tup = tuple<int, int, int, int>;

signed main() {
    int n;
    while (cin >> n) {
        priority_queue<Tup> ab[2];
        rep(i, n) {
            int a, b;
            cin >> a >> b;
            ab[0].emplace(a + b, a, b, i);
            ab[1].emplace(a + b, b, a, i);
        }

        vector<int> used(n, false);
        int score[2] = {};
        rep(i, n) {
            auto &que = ab[i&1];
            while (true) {
                int id = get<3>(que.top());
                if (used[id]) que.pop(); else break;
            }

            int ab, a, b, id;
            tie(ab, a, b, id) = que.top();
            que.pop();
            used[id] = true;
            score[i&1] += a;
            // dump(id);
            // dump(a);
            // dump(b);
        }

        cout << score[0] - score[1] << endl;
    }
}



Measured memory_bytes: 10592
use std::cmp::Ordering::*;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let a: Vec<i64> = (0..n).map(|_| read()).collect();

    if a.len() == 1 {
        println!("1");
        return;
    }

    let mut ans = 1;
    let mut flag = a[0].cmp(&a[1]);

    for i in 1..n - 1 {
        if a[i] != a[i + 1] {
            flag = match flag {
                Equal => a[i].cmp(&a[i + 1]),
                cmp => {
                    if cmp != a[i].cmp(&a[i + 1]) {
                        ans += 1;
                        Equal
                    } else {
                        flag
                    }
                }
            }
        }
    }
    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ABC
{
    class ABC164C
    {
        const bool TESTING = false;
        const string FILE = "/tmp/data.txt";

        static void Main(string[] args)
        {
            if (TESTING)
            {
                Console.SetIn(new StreamReader(FILE));
            }
            var line = Console.ReadLine();
            var sa = line.Split(' ');
            int s = int.Parse(sa[0]);
            int w = int.Parse(sa[1]);

            proc(s, w);
            if (TESTING)
            {
                Console.ReadLine();
            }
        }

        private static void proc(int s, int w)
        {
            Console.WriteLine(s > w ? "safe" : "unsafe");
        }
    }
}


Measured memory_bytes: 27384
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;

unsigned long long int a = 0, b = 0, c = 1, x = 0, y = 0, z = 0, maxy = -1, mini = 9999, counter = 0,startp=0,endp=0,checker=0,o=0,t=0;
std::vector<unsigned long long int> vec{}, vecsec{};
int iremono[100001];
std::vector<long long int>kinds{}, ans{}, kaku{};
char moji,moji2;
bool okada = true,okada2=false;
std::string output, output2, input, one, two;
unsigned long long int wanwan[100003];
int kakunou2[50][50] = {};
unsigned long long int M, A, R, C, H;

int ctoi(const char c) {
	if ('0' <= c && c <= '9') return (c - '0');
	return -1;
}
unsigned long long int LCM(unsigned long long int a, unsigned long long int b) {
	unsigned long long int i, j;
	i = a; j = b;
	while (true) {

		c = i % j;
		i = j;
		if (c != 0) {

			j = c;

		}
		else {
			break;
		}
	}
	return j * (a / j) * (b / j);
}
int main()
{

	cin >> a;

	rep(i, a) {
		cin >> b;
		vec.push_back(b);
	}
	std::sort(vec.begin(),vec.end());
	x = vec[0];

	while (true) {
	

		for (int i = 1; i < vec.size(); i++) {
			

				vec[i] = vec[i] % x;
			
			
		}
	

		std::sort(vec.begin(), vec.end());
		auto removeIt = remove_if(vec.begin(), vec.end(), [&](int value) {
			return value == 0;
		}
		);
		
		vec.erase(removeIt, vec.end());
		x = vec[0];
		if (x == 1) {
			break;

		}
		if (vec.size()==1) {
			break;
		}
	}
	cout << vec[0] << endl;
}

	
	





Measured memory_bytes: 1400
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use std::cmp::*;
use std::collections::*;
use std::mem::*;

fn main() {
    let (r, w, e) = (std::io::stdin(), std::io::stdout(), std::io::stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    assert_eq!(!0usize, std::usize::MAX); //🙊

    let (n, k) = (io.read::<usize>(), io.read::<i64>());
    let mut a = io.readn::<i64>(n);
    a.sort_by_key(|a| -a);
    let mut ans = n;
    let mut r = 0;
    for (i, &x) in a.iter().enumerate() {
        if r + x < k {
            r += x;
        } else {
            ans = min(ans, n - i - 1);
        }
    }
    io.writeln(ans);
}

static MOD: i64 = 1000000007;
static INF: i64 = std::i64::MAX >> 1;
// IO
use std::io::*;
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn chari(&mut self) -> Vec<i64> {
        self.chars()
            .iter()
            .map(|&c| (c as u8 - b'0') as i64)
            .collect::<Vec<i64>>()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
    fn debug3<S: std::fmt::Debug, T: std::fmt::Debug, U: std::fmt::Debug>(
        &mut self,
        val1: S,
        val2: T,
        val3: U,
    ) {
        writeln!(
            self.Error,
            "(debug3) {:?} -> {:?} -> {:?}",
            val1, val2, val3
        );
    }
}


Measured memory_bytes: 4352
s = input()

if s == "keyence":
    print("YES")
    exit()

for i in range(len(s)):
    for j in range(i, len(s)):
        if i == 0:
            if j < len(s) - 1:
                ans = s[j+1:]
            else:
                ans = ""
        else:
            if j < len(s) - 1:
                ans = s[:i] + s[j+1:]
            else:
                ans = s[:i]
        if ans == 'keyence':
            print("YES")
            exit()

print("NO")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(n) (n).begin(),(n).end()
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}

int main(){
	ll A,B,m;
	ll ans=0;
	cin >> A >> B >> m;
	ll a[100010],b[100010];
	ll mina=MOD,minb=MOD;
	FOR(i,A){
		cin >> a[i];
		chmin(mina,a[i]);
	}
	FOR(i,B){
		cin >> b[i];
		chmin(minb,b[i]);
	}
	ll x[100010],y[100010],c[100010];
	ans=minb+mina;
	FOR(i,m){
		cin >> x[i] >> y[i] >> c[i];
		chmin(ans,a[x[i]-1]+b[y[i]-1]-c[i]);
	}
	

	cout << ans << endl;




}

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

int main() {
    int a, b, m;
    cin >> a >> b >> m;

    vector<int> a_v(a);
    vector<int> b_v(b);
    int a_min = 100001, b_min = 100001;
    for (int i = 0; i < a; i++) {
        cin >> a_v.at(i);
        if (a_min > a_v.at(i)) a_min = a_v.at(i);
    }
    for (int i = 0; i < b; i++) {
        cin >> b_v.at(i);
        if (b_min > b_v.at(i)) b_min = b_v.at(i);
    }

    int sum_min = a_min + b_min;
    int a_i, b_i, tmp, c;
    for (int i = 0; i < m; i++) {
        cin >> a_i >> b_i >> c;
        tmp = a_v.at(a_i-1) + b_v.at(b_i-1) - c;
        if (tmp < sum_min) sum_min = tmp;
    }

    cout << sum_min << endl;
    
    return 0;
}


Measured memory_bytes: 4024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n';
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod=1e9+7;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	if(a<0) a+=mod;
}
const int N=3e3+10;
int dp[N][N],prefix[N];
int main(){
	IOS;
	int n;
	cin>>n;
	string s;
	cin>>s;
	dp[1][1]=1;
	prefix[1]=1;
	for(int len=2;len<=n;++len){
		for(int i=1;i<=len;++i){
			if(s[len-2] == '>'){
				add(dp[len][i] , prefix[len-1] - prefix[i-1]);
			}
			else{
				add(dp[len][i] , prefix[i-1]);
			}
		}
		for(int i=1;i<=len;++i){
			prefix[i]=dp[len][i];
			add(prefix[i],prefix[i-1]);
		}
	}
	int ans=0;
	for (int i = 0; i < n; ++i)
	{
		add(ans,dp[n][i+1]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 34304
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
MOD = 10 ** 9 + 7

max_digit = len(bin(max(A))) - 2

for digit in range(max_digit):
    one = np.count_nonzero((A >> digit) & 1)
    ans += (one * (N - one) * pow(2, digit, MOD)) % MOD
    ans %= MOD

print(ans)


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

void GCD( int a, int b )
{
    int count = 0;
    int r = a % b;                     //余りと値保持の変数
    a = r;

    while( r != 0 )
    {
        if( count % 2 == 0 )
        {    
            r = b % r;
            b = r;
        }
        else
        {
            r = a % r;
            a = r;
        }
        count++;
    }

    if( count % 2 == 0 )
        cout << b << endl;
    else   
        cout << a << endl;

}

int main() 
{
    int x,y;

    cin >> x >> y;

    GCD( x, y );

    return 0;
}


Measured memory_bytes: 3056
N,K = map(int,input().split())
R,S,P = map(int, input().split())
T = input()

point = 0
histry = []

for i in range(N):
    if i >= K and T[i] == histry[i-K]:
        # print('con')
        histry.append(N)
        continue
    else:
        if T[i] == 'r':
            point += P
            histry.append('r')
            # print('P')
        elif T[i] == 's':
            point += R
            histry.append('s')
            # print('R')
        elif T[i] == 'p':
            point += S
            histry.append('p')
            # print('S')

print(point)

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


int main() {
    int A,B;
    long long x; cin >> x;
    bool fin=0;
    for(A=0;A<=200;A++){
        for(B=-200;B<A;B++){
            long long a=pow(A,5)-pow(B,5);
            if(a<x){
                break;
            }
            if(a==x){
                cout << A << " " << B << endl;
                fin=1;
                break;
            }
        }
        if(fin) break;
    }
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, x;
	cin>>n>>x;
	vector<int> vec(n, 0);
	int d = 0;
	int res = 1;
	for(int i = 0; i < n; ++i)cin>>vec[i];
	for(int i = 0; i < n; ++i){d = d + vec[i]; if(d <= x)res++;}
	cout<<res<<endl;
	return 0;
}


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

int main() {
  int num, amari;
  cin >> num;
  amari = num % 10;
  
  if(amari == 2 || amari == 4 || amari == 5 || amari == 7 || amari == 9){
    cout << "hon" << endl;
  } else if(amari == 0 || amari == 1 || amari == 6 || amari == 8){
    cout << "pon" << endl;
  } else if (amari == 3) {
    cout << "bon" << endl;
  }
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inf = 1000000000;
typedef pair<ll, ll> P;
int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if (a > b||(n==1&&a!=b)) {
		cout << "0" << endl;
		return 0;
	}
	if (n == 1 && a == b) {
		cout << "1" << endl;
		return 0;
	}
	
	ll sum;
	sum = (a + b + (n - 2) * b) - (a + b + (n - 2) * a)+1;
	cout << sum << endl;
	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int MAX;

//int memo[810][810][9];

int gcd(int a, int b){
	  return (a==0) ? b : gcd(b%a,a);
}

pii frac_minus(int p,int q, int mp, int mq){ // p/q - mp/mq
	  int nume = p*mq - q*mp;
	  int deno = q*mq;
	  int g = gcd(nume,deno);
	  return pii(nume/g, deno/g);
}

int solve(int p,int q, int prod,int n,int pre){
	  
	  if(prod > MAX or p < 0 or q < 0)
			return 0;
	  if(n<0)
			return 0;

	  int ans = 0;
	  if(p==0)
			ans++;
	  int high = 12000;
	  if(p!=0)
			high = min(MAX,q*n/p);
	  for(int j=pre; j<=high; j++){
			pii tmp = frac_minus (p,q,1,j);
			int np = tmp.first;
			int nq = tmp.second;
			if(prod*j > MAX) break;
			ans += solve(np,nq,prod*j,n-1,j);
	  }

	  return ans ;
}

int main(){

	  while(1){

			int p,q,n;
			cin >> p >> q >> MAX >> n;
			if(!p) break;
			int g = gcd(p,q);
			cout << solve(p/g,q/g,1,n,1) << endl;
	  }
}

Measured memory_bytes: 1160
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long lll;
const int MAXN=100000+3;
lll n;
lll a[MAXN];
lll b[MAXN];
lll cnt;
lll ans;
int main(){
	scanf("%lld",&n);
	for(lll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]<0){
			cnt++;
		}
		if(a[i]<0){
			b[i]=a[i]-a[i]*2;
		}
		else{
			b[i]=a[i];
		}
		ans+=b[i];
	}
	sort(b+1,b+n+1);
	if(cnt%2==1){
		ans-=b[1]*2;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <cmath>
#define MAX (int)2e5
typedef long long int ll;
using namespace std;
ll cood[MAX];
int main(void){
  int N;
  ll D;
  int ans=0;
  cin >> N >> D;
  for(int i=0;i<N;i++){
    ll x,y;
    cin >> x >> y;
    ll num = x*x + y*y;
    if(num <= D*D)
      ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628