akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_set>
#include<unordered_map>
using namespace std;

const double pi=4*atan(1.0);

int main() {
	int N,A,X;
	cin>>N>>A;
	X=A;
	vector<int> arr(N);
	for(auto& val:arr){
		cin>>val;
		X=max(X,val);
		val-=A;
	}
	
	vector<vector<long long>> dp(N,vector<long long>(2*N*X,0));
	int offset=N*X;
	dp[0][offset]=1;
	++dp[0][offset+arr[0]];

	for(int i=1;i<N;++i){
		for(int j=0;j<2*offset;++j){
			dp[i][j]=dp[i-1][j];
			if(j-arr[i]>=0 && j-arr[i]<2*offset){
				dp[i][j]+=dp[i-1][j-arr[i]];
			}
		}
	}

	cout<<dp[N-1][offset]-1<<endl;

	//system("pause");
	return 0;
}


Measured memory_bytes: 2176
def check(f):
    for winner in range(2):
        for i in range(3):
            ok=True
            for j in range(3):
                if(f[i][j]!=winner):ok=False
            if ok:
                return winner
        for j in range(3):
            ok=True
            for i in range(3):
                if(f[i][j]!=winner):ok=False
            if ok:
                return winner
        for k in range(1):
            ok=True
            for i in range(3):
                if(f[i][i]!=winner):ok=False
            if ok:
                return winner
        for k in range(1):
            ok=True
            for i in range(3):
                if(f[i][2-i]!=winner):ok=False
            if ok:
                return winner
    return -1


while True:
    try:
        st=input()
        f=[[-1 for i in range(3)]for j in range(3)]
        for i in range(3):
            for j in range(3):
                n=i*3+j
                if(st[n]=='o'):
                    f[i][j]=0
                elif st[n]=='x':
                    f[i][j]=1
                else:
                    f[i][j]=-1
        ans=check(f)
        if(ans==1):
            print('x')
        elif ans==0:
            print('o')
        else:
            print('d')
    except:
        break

Measured memory_bytes: 7552
#include<stdio.h>


int main(){
  int i,j=0,s,v,N;
  scanf("%d",&N);
  int A[N];
  for(i=0;i<=N-1;i++){
    scanf("%d",&A[i]);
     }
  for(i=1;i<=N;i++){
    v=A[i];
    j=i-1;
     for(s=0;s<=N-1;s++){
      if(s<N-1)
      printf("%d ",A[s]);
      else printf("%d",A[s]);
    }
    printf("\n");
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
  }

  return 0;
}



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

int main() {

  int count=0;
  string S; cin>>S;
  for(int i=0; i<S.length()/2;i++){
    if(S.at(i)!=S.at(S.length()-1-i)){
      count++;}
  }

	cout<<count<<endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::cmp::*;

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

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

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

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

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

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

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

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


fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn abc(X: i64, x:Vec<i64>) -> i64 {
    let mut res = 0;
    for &x_ in x.iter() {
        res = gcd(res, (x_ - X).abs());
    }
    return res
}


fn main() {
    /*
    assert_eq!(abc(), "Yes");
    assert_eq!(abc(101), "No");
    assert_eq!(abc(999999999), "Yes");
    */
    input!{
        n: usize,
        X: i64,
        x: [i64; n],
    }
    let result = abc(X, x);

    println!("{}", result);
}


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    int A, B, M;
    cin >> A >> B >> M;


    vector<int> a(A);
    FOR(i, A) cin >> a[i];

    vector<int> b(B);
    FOR(i, B) cin >> b[i];

    int mina = a[0];
    FOR(i, A) mina = min(mina, a[i]);

    int minb = b[0];
    FOR(i, B) minb = min(minb, b[i]);

    int sol = mina + minb;

    FOR(i, M){
        int x, y, c;
        cin >> x >> y >> c;
        sol = min(sol, a[x-1] + b[y-1] - c);
    }
    cout << sol << endl;


    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

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

int main() {
    int n, m;
    cin >> n;
    vector<string> blue(n);
    for (int i=0; i<n; i++) {
        cin >> blue[i];
    }
    cin >> m;
    vector<string> red(m);
    for (int i=0; i<m; i++) {
        cin >> red[i];
    }
    auto calc = [&](string s){
        int buf = 0;
        for (string t: blue) {
            if (s == t) buf++;
        }
        for (string t: red) {
            if (s == t) buf--;
        }
        return buf;
    };
    int ans = 0;
    for (string t: blue) {
        ans = max(ans, calc(t));
    }
    cout << ans << endl;
    return 0;
}

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


int main() {
    int a;
    cin >> a;
    cout << "Christmas ";
    for(int i = 0; i < (25 - a); i++){
        cout << "Eve ";
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<ll> l(n);
  REP(i, n) { cin >> l[i]; }
  sort(all(l));
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        if (l[i] == l[j] || l[j] == l[k]) {
          continue;
        }
        if (l[i] + l[j] > l[k]) {
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

int gx,gy,count;
int map[17][17]={} ;
int dx[] = { 0,1 } , dy[] = { 1,0 } ;

void road_sum( int nx , int ny ){
	if( map[nx][ny] == 2 ) count++;
	else{
		for( int i=0 ; i<2 ; i++ ){
			if( nx+dx[i] <= gx && ny+dy[i] <= gy && map[nx+dx[i]][ny+dy[i]] != 1 )
					road_sum( nx+dx[i] , ny+dy[i] ) ;
		}
	}
}

int main(){
	
	int n,x,y ;
	
	while(1){
		cin >> gx >> gy ;
		if( gx==0 && gy==0 ) break ;
		cin >> n ;
		
		map[gx][gy] = 2 ;
		count = 0 ;
		
		for( int i=0 ; i<n ; i++ ){
			cin >> x >> y ;
			map[x][y] = 1 ;
		}
		
		road_sum(1,1) ;
		
		cout << count << endl ;
		
		for( int i=0 ; i<17 ; i++ )
			for( int j=0 ; j<17 ; j++ )
				map[i][j] = 0 ;
	}
	return 0;
}

Measured memory_bytes: 1160
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
print(S.count("ABC"))


Measured memory_bytes: 5840
#include<iostream>
#include<stdio.h>
#include<string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<unsigned int> a(N, 0);
	for (int i = 0; i < N; ++i){
		cin >> a[i];
	}

	int value = 1;
	for (int i = 0; i < N; ++i) {
		if (a[i] == value) {
			value++;
		}
	}

	if (value == 1){
		printf("-1\n");
	} else {
		printf("%d\n", N - (value - 1));
	}

	return 0;
}


Measured memory_bytes: 1024
import sys
from bisect import bisect_right, bisect_left
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))
    A.sort()
    B.sort()
    C.sort()
    ans = 0
    for i in range(N):
        top = bisect_left(A, B[i])
        bottom = bisect_right(C, B[i])
        if top>0 and bottom != N:
            ans += top*(N-bottom)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 21580
use std::cmp::*;

// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let n: usize = read();
    let mut a: Vec<u64> = read_vec();
    let b: Vec<u64> = read_vec();
    let mut killed_enemy: u64 = 0;

    // 後ろから処理
    for i in (0..n).rev()
    {
        // 討伐可能数
        let mut power = b[i];

        // i + 1番目の街の敵を可能な限り倒す
        let mut possible_subjugation = min(a[i + 1], power);
        killed_enemy += possible_subjugation;
        // 倒しただけ討伐可能数を減少
        power -= possible_subjugation;
        // 街の残敵数を減らす
        a[i + 1] -= possible_subjugation;

        // 討伐可能数が0であれば次へ
        if power == 0 { continue; }

        // i番目の街の敵を可能な限り倒す
        possible_subjugation = min(a[i], power);
        killed_enemy += possible_subjugation;
        // 街の残敵数を減らす
        a[i] -= possible_subjugation;
    }

    println!("{}", killed_enemy);
}


Measured memory_bytes: 9972
#include<bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<long long , long long>
#define pb push_back
#define ll long long
#define ld long double
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define fill(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
ll power(ll x,ll y,ll m){ll r=1;for(;y;y>>=1){if(y&1)r=r*x%m;x=x*x%m;}return r;}
const ll mod = 1e9 + 7;
const ld pi = 3.14159265358979;

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

bool valid(int a, int b, int c, int d){
    if(a >= 0 && b >=0 && a <= c-1 && b <= d-1){
        return true;
    }
    return false;
}

int run_test(){
    int h, w, a, b, c, d;
    cin >> h >> w >> a >> b >> c >> d;
    a--; b--; c--; d--;
    int arr[h][w];
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char t;
            cin >> t;
            arr[i][j] = (t == '#');
        }
    }
    int visited[h][w];
    fill(visited, 0);
    deque<pair<pll, ll>> q;
    q.push_front({{a, b}, 0});
    while(!q.empty()){
        pll pos = (q.front()).ff;
        ll cost = (q.front()).ss;
        if(pos.ff == c && pos.ss == d){
            cout << cost;
            return 0;
        }
        q.pop_front();
        if(visited[pos.ff][pos.ss]) continue;
        visited[pos.ff][pos.ss] = 1;
        for(int i=0; i<4; i++){
            int nr = pos.ff + dr[i];
            int nc = pos.ss + dc[i];
            if(valid(nr, nc, h, w) && !visited[nr][nc] && arr[nr][nc] == 0){
                q.push_front({{nr, nc}, cost});
            }
        }
        for(int i=-2; i <= 2; i++){
            for(int j=-2; j<=2; j++){
                int nr = pos.ff + i;
                int nc = pos.ss + j;
                if(valid(nr, nc, h, w) && !visited[nr][nc] && arr[nr][nc]== 0){
                    q.push_back({{nr, nc}, cost + 1});
                }
            }
        }
    }
    cout << -1; 
    return 0;
}
 
int main(){
    FAST;
    ll t;
    t = 1;
 
    while(t--){
        run_test();
    }
}

Measured memory_bytes: 12984
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>

using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll MASK = (1 << 18) - 1;
ll ans, n, a[500], b[500];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (int i = 0; i < n; i++)
    {
        ans += max(0LL, a[i] - b[i]);
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

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

  int n;
  cin >> n;
  int t[n], x[n], y[n];
  for(int i = 0; i < n; i++){
    cin >> t[i] >> x[i] >> y[i];
  }

  int sx = 0, sy = 0, st = 0;
  for(int i = 0; i < n; i++){
    int diff = abs(sx - x[i]) + abs(sy - y[i]);
    int rt = t[i] - st;
    if(rt < diff){
      cout << "No" << endl;
      return 0;
    }
    if((rt - diff) % 2 == 0){
      st = t[i]; sx = x[i]; sy = y[i];
    }
    else{
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

typedef vector<ll> vecll;
typedef vector<ld> vecld;
typedef vector<bool> vecbl;
typedef vector<vector<ll> > matll;
typedef vector<vector<ld> > matld;
typedef vector<vector<bool> > matbl;
#define mp make_pair;

const ll prime = 1000000000 + 7;
const ld PI = 2 * acos(0.0);

/*
cout << fixed << setprecision(10);
*/

bool my_comp(pll a, pll b) {
	if (a.first != b.first) {
		return a.first < b.first;
	}

	return a.second < b.second;
}

ll rec(ll n, vecll a, matll x, matll y, vecll list, ll index) {
	switch (list[index]) {
	case 0:
		// 不親切確定
		if (index < n - 1) {
			return rec(n, a, x, y, list, index + 1);
		}
		else {
			ll sum = 0;
			for (ll i = 0; i < n; i++)
			{
				if (list[i] == 1) {
					sum++;
				}
			}
			return sum;
		}
		break;
	case 1:
		// 親切確定
		for (ll i = 0; i < a[index]; i++)
		{
			ll xv = x[index][i];
			ll yv = y[index][i];
			if (list[xv] == 2) {
				list[xv] = yv;
			}
			else if (list[xv] != yv) {
				//矛盾
				return 0;
			}
		}
		if (index < n - 1) {
			return rec(n, a, x, y, list, index + 1);
		}
		else {
			ll sum = 0;
			for (ll i = 0; i < n; i++)
			{
				if (list[i] == 1) {
					sum++;
				}
			}
			return sum;
		}
		break;

	case 2:
		//不明確のとき
		ll v1, v2;
		list[index] = 0;
		v1 = rec(n, a, x, y, list, index);
		list[index] = 1;
		v2 = rec(n, a, x, y, list, index);
		return max(v1, v2);
		break;
	}
}

int main() {

	ll n;
	cin >> n;
	vecll a(n);
	matll x(n);
	matll y(n);
	ll k;
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
		for (ll j = 0; j < a[i]; j++)
		{
			cin >> k;
			k--;
			x[i].push_back(k);
			cin >> k;
			y[i].push_back(k);
		}
	}

	ll ans;
	ll index = 0;
	vecll list(n, 2);
	ans = rec(n, a, x, y, list, index);
	cout << ans << endl;
	

	return 0;
}


Measured memory_bytes: 1016
# SPDX-License-Identifier: X11
# 2020-08-30
# Multiplication 4 (500pt)

const M = 1000000007

function main()
  N, K = parse.(Int, split(readline(), " "))
  A = parse.(Int, split(readline(), " "))
  T = 1

  X = maximum(A)
  if X == 0 && K & 1 == 1
    println(0)
    return
  elseif N == K
    for i ∈ A
      T *= i ⨳ M
      T = T ⨳ M
    end
    println(T)
    return
  end

  sort!(A; lt = test, rev = true)

  if X < 0 && K & 1 == 1
    B = A[end + 1 - K:end]
  elseif X <= 0 && K & 1 == 0
    B = A[1:K]
    if B[K] == 0
      println(0)
      return
    end
  else
    B = A[1:K]
    if oddneg(B)
      if A[K + 1] == 0
        println(0)
        return
      end

      R = A[K + 1:end]
      rfp = firstpos(R) === nothing ? -1 : firstpos(R)
      rfpv = rfp == -1 ? rfp : R[rfp]
      rfn = firstneg(R) === nothing ? -1 : firstneg(R)
      rfnv = rfn == -1 ? rfn : abs(R[rfn])
      blp = lastpos(B)
      blpv = blp === nothing ? blp : B[blp]
      bln = lastneg(B)
      blnv = abs(B[bln])

      if blp === nothing || rfpv//blnv > rfnv//blpv
        B[bln] = R[rfp]
      elseif rfpv//blnv < rfnv//blpv
        B[blp] = R[rfn]
      elseif rfpv//blnv == rfnv//blpv
        B[K] = B[K] < 0 ? R[rfp] : R[rfn]
      end
    end
  end

  for i ∈ B
    T *= i ⨳ M
    T = T ⨳ M
  end

  println(T)
end

function test(x::Int, y::Int)
  return abs(x) == abs(y) ? x < y : abs(x) < abs(y);
end

⨳(x, y) = mod(x, y)
oddneg(A) = count(x -> x < 0, A) & 1 == 1
firstneg(A) = findfirst(x -> x < 0, A)
firstpos(A) = findfirst(x -> x > 0, A)
lastneg(A) = findlast(x -> x < 0, A)
lastpos(A) = findlast(x -> x > 0, A)

main()


Measured memory_bytes: 213816
#include <vector>
#include <iostream>
using namespace std;
int n, u, v, m, x;
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> u >> v >> m;
	vector<int> p1(1000000, -1), p2(1000000, -1);
	vector<int> q1(1000000, -1), q2(1000000, -1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x; x--;
			p1[x] = i;
			p2[x] = j;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x; x--;
			q1[x] = i;
			q2[x] = j;
		}
	}
	int pret = 0, qret = 0;
	bool flag = false;
	vector<int> pc1(n, 0), pc2(n, 0); int pc3 = 0, pc4 = 0;
	vector<int> qc1(n, 0), qc2(n, 0); int qc3 = 0, qc4 = 0;
	while (m-- && !flag) {
		cin >> x; x--;
		if (p1[x] != -1) {
			pc1[p1[x]]++; if (pc1[p1[x]] == n) pret++;
			pc2[p2[x]]++; if (pc2[p2[x]] == n) pret++;
			if (p1[x] == p2[x]) {
				pc3++;
				if (pc3 == n) pret++;
			}
			if (p1[x] == n - p2[x] - 1) {
				pc4++;
				if (pc4 == n) pret++;
			}
		}
		if (q1[x] != -1) {
			qc1[q1[x]]++; if (qc1[q1[x]] == n) qret++;
			qc2[q2[x]]++; if (qc2[q2[x]] == n) qret++;
			if (q1[x] == q2[x]) {
				qc3++;
				if (qc3 == n) qret++;
			}
			if (q1[x] == n - q2[x] - 1) {
				qc4++;
				if (qc4 == n) qret++;
			}
		}
		if (n == 1) {
			if (pret > 1) pret = 1;
			if (qret > 1) qret = 1;
		}
		if (pret >= u && qret >= v) break;
		if (pret >= u) {
			cout << "USAGI" << endl;
			flag = true;
		}
		if (qret >= v) {
			cout << "NEKO" << endl;
			flag = true;
		}
	}
	if (!flag) cout << "DRAW" << endl;
	return 0;
}

Measured memory_bytes: 18420
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
int main(){
  int S;
  int W;
  rd(S);
  rd(W);
  if(S <= W){
    wt_L("unsafe");
    wt_L('\n');
  }
  else{
    wt_L("safe");
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20200419-1

// --- original code ---
// {
//   int S, W;
//   rd(S, W);
//   wt(if[S <= W, "unsafe", "safe"]);
// }


Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

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

	scanf("%d%d%d", &A, &B, &C);

	if (C - (A - B) < 0)
		printf("0\n");
	else	
		printf("%d", C - (A - B));
	
}


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 924844033

typedef long long ll;
typedef pair<ll,ll> P;

bool used[2222];
ll  dp[4444][2222];
ll kaijo[2222];

int main(){
	
	ll n,k;cin >> n >> k;
	vector<int> v;
	ll sum = 0;
	ll edgeId = 1, PathId = 0;
	
	kaijo[0] = 1;
	REP(i,2221)kaijo[i+1] = (kaijo[i] * (i+1)) % MOD;
	
	REP(i,n){
		if(!used[i]){
			used[i] = true;
			ll num = i + k;
			ll cou = 0;
			while(num < n && !used[num]){
				used[num] = true;
				cou++;
				num += k;
			}
			if(cou){
				v.PB(cou);
				v.PB(cou);
				sum += 2 * cou;
			}
		}
	}
	
	dp[0][0] = 1;
	REP(i,sum){
		ll tasi = 2;
		if(edgeId == v[PathId]){
			edgeId = 0;
			PathId++;
			tasi--;
		}
		
		REP(j, 2220){
			dp[i + 1][j] += dp[i][j];
			dp[i + tasi][j+1] += dp[i][j];
			dp[i + 1][j] %= MOD;
			dp[i + tasi][j+1] %= MOD;
		}
		edgeId++;
	}
			
	edgeId = 1;
	ll ans = 0;
	REP(i,n+1){
		ans += dp[sum][i] * kaijo[n - i] * edgeId + MOD;
		ans %= MOD;
		edgeId *= -1;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 69888
// template.cpp {{{
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
#define reps(i, a, n) for (lint i = (a); i < (lint)(n); ++i)
#define rep(i, n) reps(i, 0, n)
struct pre_{pre_(){cin.tie(0);ios::sync_with_stdio(0);}} pre__;
// }}}

signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  int b;
  rep(i, m) cin >> a[i] >> b;
  sort(begin(a), end(a), greater<int>());
  int res = 0;
  rep(i, m - 1) {
    if (a[i] < n) {
      res += n - a[i];
    }
  }
  cout << res << endl;
}

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

/* define const */

/* finish defineing const */

long n, m;

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

    long cnt = 0;
    // cが足りないとき
    if (n > m / 2)
    {
        cnt = m / 2;
    }
    else
    {
        // sがなくなるまで作る
        cnt = n;

        // scc分のcを減らす.
        m = m - 2 * n;

        // cを組み合わせてsを作る
        cnt += m / 4;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define M(a,b) memset(a,b,sizeof(a))
const int MAXN = 1e5+5;
int n,t;
int num[MAXN];
int mnum[MAXN];
int main()
{
    while(~scanf("%d %d",&n,&t))
    {
        for(int i=0;i<n;i++) scanf("%d",&num[i]);

        mnum[n-1] = num[n-1];
        for(int i=n-1;i>0;i--) mnum[i-1] = max(mnum[i],num[i-1]);

        int MAX = 0;

        for(int i=0;i<n;i++) MAX = max(mnum[i]-num[i],MAX);
        int sum = 0 ;

        for(int i=0;i<n;i++) if(mnum[i]-num[i]==MAX) sum++;
        printf("%d\n",sum);
    }
    return 0;
}


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

int main(){
    int n;
    cin>>n;
    map<ll,ll>mpx;
    map<ll,ll>mpy;
    vector<int>a(n);
    rep(i,n){
        cin>>a[i];
    }
    rep(i,n){
        mpx[a[i]]++;
    }
    ll mx=0;
    ll my=0;
    for(auto p:mpx){
        if(p.second>=2){
            mx=max(mx,p.first);
        }
    }
    sort(a.begin(),a.end());
    int cnt=0;
    rep(i,n){
        if(a[i]==mx){
            a[i]=0;
            cnt+=1;
            if(cnt==2)break;
        }
    }
    rep(i,n){
        mpy[a[i]]++;
    }
    for(auto p:mpy){
        if(p.second>=2){
            my=max(my,p.first);
        }
    }
    
    cout<<mx*my<<endl;
}

    


Measured memory_bytes: 13184
import java.util.*;


public class Main {

	/**
	 * @param args
	 */
	
	static Scanner sc = new Scanner(System.in);
	//static final double EPS = 1e-10;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		double y;
		while(sc.hasNextDouble()) {
			y = y(sc.nextDouble());
			int ans = 1;
			while(h(ans) < y) ans++;
			System.out.println(ans);
		}
	}
	
	static double y(double v) {
		return 0.0510204081632653 * v * v;
	}
	
	static double h(int n) {
		return (double)(5 * n - 5);
	}

}

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

using namespace std;

int main()
{
    #ifdef LOCAL_EXEC
    #else
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif // LOCAL_EXEC
    long long int n,i,j=0,k;
    string s,t;
    cin>>s;
    cin>>t;
    for(i=0;i<s.size();i++){
        if(s[i]!=t[i])
            j+=1;
    }
    cout<<j;
    return 0;
}


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


int main(int argc, char const *argv[]) {
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> cost(n);
    vector<vector<int> > a(n, vector<int>(m));

    for (size_t i = 0; i < n; i++) {
        cin >> cost[i];
        for (size_t j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    vector<int> check(m);
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            check[j] += a[i][j];
        }
    }
    bool can = true;
    for (size_t j = 0; j < m; j++) {
        if (check[j] < x) {
            can = false;
            break;
        }
    }
    if (!can) {
        cout << "-1" << endl;
        return 0;
    }

    int min_cost = 1e9;
    for (size_t bit = 0; bit < (1<<n); bit++) {
        vector<int> abi(m);
        int temp = 0;
        for (size_t i = 0; i < n; i++) {
            if (bit & 1<<i) {
                temp += cost[i];
                for (size_t j = 0; j < m; j++) {
                    abi[j] += a[i][j];
                }
            }
        }

        bool can = true;
        for (size_t j = 0; j < m; j++) {
            if (abi[j] < x) {
                can = false;
                break;
            }
        }

        if (can) {
            min_cost = min(min_cost, temp);
        }
    }

    cout << min_cost << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int N;
int A[100000];

int main(int argc, char **argv) {
	cin >> N;
	REP(i, N) cin >> A[i];
	ll res = 0;
	REP(i, N - 1) {
		res += A[i] / 2;
		A[i] %= 2;
		if (A[i] >= 1 && A[i + 1] >= 1) {
			--A[i]; --A[i + 1];
			++res;
		}
	}
	res += A[N - 1] / 2;
	cout << res << endl;
	return 0;
}


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

using ll = long long int;
using llu = unsigned long long int;
using ld = long double;
const long long int NUM = 1000000;
const long double PI = 2*acos(0.0);
const int INF = 1e9 + 10 ;
const long long int maximum = (-1*INF);
#define LCM(a,b)            (a / __gcd(a,b)) * b
#define GCD(a,b)            __gcd(a,b)
#define dist(x1,y1,x2,y2)   sqrtl((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
#define sqr(a)              ((a)*(a))
#define fast                ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define precision(a)        fixed<<setprecision(a)
#define endl                "\n"
#define pb                  push_back
#define bp                  pop_back
#define pf                  push_front
#define fp                  pop_front
#define mp                  make_pair
#define ff                  first
#define ss                  second
#define ub                  upper_bound
#define lb                  lower_bound
#define all(x)              x.begin(), x.end()
#define debug(x)            cout<<"debug "<<x<<"\n"
#define ms(a,b)             memset((a),(b),sizeof(a))
#define min3(a,b,c)         min(a,min(b,c))
#define max3(a,b,c)         max(a,max(b,c))
#define min4(a,b,c,d)       min(min(a,b),min(c,d))
#define max4(a,b,c,d)       max(max(a,b),max(c,d))
#define max5(a,b,c,d,e)     max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e)     min(min3(a,b,c),min(d,e))
#define REP(i,b)            for(long long int i = 0; i < b; i++)
#define READ(f)             freopen("f", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)

/*void sieve(ll n) {
    bool status[(n>>1)+1] = {false};
    ll inc, i;
    for(i = 3; i*i <= n; i += 2)
    {
        if(!status[i>>1])
        {
            inc = i<<1;
            for(ll j = i*i; j <= n; j += inc)
                status[j>>1] = true;
        }
    }
}*/

/*bool compare(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
    if(a.ff == b.ff)
        return a.ss <= b.ss;
    return a.ff < b.ff;
}*/


/*ll logs(ll x)
{
    return 64 - __builtin_clzll(x) - 1;
}*/

//map<char, ll> m = { {'q', 9}, {'r', 5}, {'b', 3}, {'n', 3}, {'p', 1}, {'k', 0}, {'.', 0} };

//||

int main() {
    fast;
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll sum = min(a, k);
    k = max((ll)0, k-b-a);
    if (k) sum -= min(c, k);
    cout << sum;
    return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>

int main(){
  int len = 0, i = 0;
  char s[100001], t[50001];
  
  scanf("%s", s);
  while(s[len]){
    if(len%2 == 0){
      t[i++] = s[len];
    }
    len++;
  }
  t[i] = '\0';
  
  printf("%s\n", t);
  
  return 0;
}

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

int main(){
    ll k; cin >> k;
    ll ans = 0;
    rep(i,k){
        rep(j,k){
            rep(l,k){
                ans += gcd(gcd(i+1,j+1),l+1);
            }
        }
    }

    cout << ans << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    int n,m,k;
    cin >>n>>m>>k;
    vector<int>a(n);
    vector<int>b(m);
    for (int i = 0; i < n; ++i)cin >>a[i];
    for (int i = 0; i < m; ++i)cin >>b[i];
    vector<ll>suma(n+1,0);
    vector<ll>sumb(m+1,0);
    for (int i = 0; i < n; ++i) {
        suma[i+1]=suma[i]+a[i];
    }
    for (int i = 0; i < m; ++i) {
        sumb[i+1]=sumb[i]+b[i];
    }
    ll c=k;
    int ans=0;
    for (int i = 0; i <= n; ++i) {
        int now=0;
        now=i;
        c=k;
        c-=suma[i];
        if(c<0)break;
        int id=upper_bound(all(sumb),c)-sumb.begin();
        id--;if(id<0)id=0;
        ans=max(ans,now+id);
    }
    cout <<ans <<endl;
}


Measured memory_bytes: 7940
#include <bits/stdc++.h>
using namespace std;
 
#define int         long long
#define endl        "\n"
#define pii         pair<int, int>
 
 
void solve(int TC) {
    int r, c; cin >> r >> c;
    char a[r][c];
    for(int i=0; i<r; i++) for(int j=0; j<c; j++) cin >> a[i][j];
    char b[r+2][c+2];
    for(int i=0; i<r+2; i++) for(int j=0; j<c+2; j++) b[i][j] = '#';
    for(int i=1; i<=r; i++) for(int j=1; j<=c; j++) b[i][j] = a[i-1][j-1];
    for(int i=0; i<r+2; i++) {
        for(int j=0; j<c+2; j++) {
            cout << b[i][j];
        }
        cout << endl;
    }
}
 
signed main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);
 
 
    int T = 1;
    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve(i);
    }
    return 0;
 
}

Measured memory_bytes: 3648
N,M=map(int,input().split())
b=[list(map(int,input().split())) for i in range(M)]
import sys
lists=[]
for i in range(N):
  lists.append(0)
try:
  for i1 in range(0,M):
    for i2 in range(i1,M):
      if b[i1][0]==b[i2][0] and b[i1][1]!=b[i2][1]:
        print (-1)
        sys.exit()
      else:
        lists[b[i1][0]-1]=b[i1][1]
except IndexError:
  print (-1)
  sys.exit()
for i3 in range(M):
  if b[i3][0]==1 and b[i3][1]==0 and N!=1:
    print (-1)
    sys.exit()
s=0
for i in range(N):
  s=s+lists[i]*10**(N-1-i)
if s>=10**N:
  print (-1)
elif N==1 and s==0:
  print (0)
elif s<10**(N-1):
  s=s+10**(N-1)
  print (s)
else:
  print (s)

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

using namespace std;

const int MAX = 100001;

long long A[MAX], B[MAX];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld %lld", &A[i], &B[i]);
	long long ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		A[i] += ans;
		if (A[i] < B[i] && A[i] != 0) {
			ans += (B[i] - A[i]);
			continue;
		}
		if (A[i] % B[i] == 0)
			continue;
		ans += (B[i] - (A[i] % B[i]));
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using i64 = long long;

long long *fact, *inv;

template <class T>
T pow(T x, T n, T mod) {
    T ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

template <class T>
T inverse(T x, T p) { return pow(x, p - 2, p); }

void init_factorial(int n, long long mod) {
    fact = new long long[n + 1];
    inv = new long long[n + 1];
    fact[0] = 1;
    for (long long i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    inv[n] = inverse(fact[n], mod);
    for (long long i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

int main() {
    i64 n, a, b, c;
    constexpr i64 mod = 1000000007;
    std::cin >> n >> a >> b >> c;
    init_factorial(2 * n, mod);
    i64 co = 100ll * inverse((100 - c) * (100 - c), mod) % mod;
    i64 r = inverse(a + b, mod);
    i64 d = pow(r, n, mod), an = pow(a, n, mod), bn = pow(b, n, mod);
    i64 ret = 0, bp = 1, ap = 1;
    for (i64 i = 0; i < n; i++) {
        ret = (ret + fact[n + i - 1] * inv[i] % mod * inv[n - 1] % mod * (a + b) % mod * (n + i) % mod * d % mod * (an * bp % mod + ap * bn % mod) % mod) % mod;
        d = d * r % mod;
        ap = ap * a % mod;
        bp = bp * b % mod;
    }
    std::cout << co * ret % mod << std::endl;

    return 0;
}


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

int abs(int x, int y) { return x > y ? x - y : y - x; }

int main(){
	vector<int> ansvec;
	for (;;){
		int n, m;
		cin >> n >> m;
		if (n == 0) break;

		set<int> tarocards;
		int tarosum = 0;
		for (int i = 0; i < n; i++){
			int s;
			cin >> s;
			tarocards.insert(s);
			tarosum += s;
		}
		set<int> hanakocards;
		int hanakosum = 0;
		for (int i = 0; i < m; i++){
			int s;
			cin >> s;
			hanakocards.insert(s);
			hanakosum += s;
		}

		if (abs(hanakosum - tarosum) % 2 == 1){
			ansvec.push_back(-1);
			continue;
		}

		int taroans = -1, hanakoans = -1;
		int tmpcardsum = 1000;
		for (auto it = tarocards.begin(); it != tarocards.end(); it++){
			int tmptaroans = *it;
			int tmphanakoans = (hanakosum - tarosum + 2 * tmptaroans) / 2;
			if (hanakocards.count(tmphanakoans) > 0 && (tmptaroans + tmphanakoans) < tmpcardsum){
				taroans = tmptaroans;
				hanakoans = tmphanakoans;
				tmpcardsum = tmptaroans + tmphanakoans;
			}
		}

		if (taroans > 0){
			ansvec.push_back(taroans);
			ansvec.push_back(hanakoans);
		}
		else{
			ansvec.push_back(-1);
		}
	}
	
	for (auto it = ansvec.begin(); it != ansvec.end(); it++){
		cout << *it;
		if (*it != -1) cout << " " << *(++it);
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1216
count = 0
temp_count = 0
for s in str(input().split()):
    if s == 'A' or s == 'G' or s == 'T' or s == 'C':
        temp_count += 1
        if temp_count > count:
            count = temp_count
    else:
        temp_count = 0
print(count)

Measured memory_bytes: 2940
#include <cstdio>
#include <cstring>

int main()
{
	char s[100001];
	scanf("%s", s);
	int l = strlen(s);
	int min = l;
	for (int i = 1; i < l; i++) {
		if (s[i - 1] != s[i]) {
			int t = i > l - i ? i : l - i;
			min = min > t ? t : min;
		}
	}
	printf("%d\n", min);
	return  0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1000003;
const int N = 2000010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    x %= mod;
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    x %= mod;
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

ll calc(ll x, ll d, ll n){
    if (d == 0) return powll(x, n);
    if (x == 0) return 0;
    if (n >= mod) return 0;
    ll s = divll(x, d);
    ll t = divll(x + (n - 1) * d, d);
    if (s > t) return 0;
    ll ret = powll(d, n);
    ret = (ret * nPr(t, t - s + 1)) % mod;
    return ret;
}

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

    fact[0] = invf[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
        invf[i] = divll(invf[i-1], i);
    }

    while (q--){
        ll x = in(), d = in(), n = in();
        printf("%lld\n", calc(x, d, n));
    }
    return 0;
}

Measured memory_bytes: 32128
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
#include <sstream>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
 
 
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll ans = 0;
    ll a,b,c,d; cin >> a >> b >> c >> d;
    while (a > 0 && c > 0) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    return 0;
} 

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

int main() {
  string S;
  cin>>S;
  int ans(0);
  for (int i(0);i<S.size();i++){
    int cnt(0);
    for (int j(i);j<S.size();j++){
      if (S[j] == 'A' || S[j] == 'G' ||S[j] == 'C' ||S[j] == 'T' )cnt+=1;
      else break;
    }
    ans=max(ans,cnt);
  }
  cout << ans<<endl;
  return 0;
}


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




int main() {
	int c[5],cnt=0, cnt1=0;
	char s[5];
	scanf("%s", s);
	for (int i = 0; i < 5; i++) {
		
		 c[i] = s[i] - '0';
	}
	int a = c[0] * 10 + c[1];
	int b = c[2] * 10 + c[3];
	if (a>0 &&a<= 12)cnt++;
	if (b>0&&b <= 12)cnt1++;
	
	if (cnt1 == 1 && cnt == 1)puts("AMBIGUOUS");
    if (cnt1 == 0 && cnt == 1)puts("MMYY");
	if (cnt1 == 1 && cnt == 0)puts("YYMM");
	if (cnt1 == 0 && cnt == 0)puts("NA");
	return 0;
}

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

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

  int left = 0, right = n - 1;
  int cnt = 0;
  while (1) {
    while (s[left] != 'W') {
      left++;
      if (left > n - 1) {
        break;
      }
    }
    while (s[right] != 'R') {
      right--;
      if (right < 0) {
        break;
      }
    }
    if (left >= right) {
      break;
    } else {
      cnt++;
      left++;
      right--;
      if (left > n - 1 || right < 0) {
        break;
      }
    }
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3748
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, = map(int, input().split())
S = input().strip()

ans = 0
for i in range(1000):
    s = str(i).zfill(3)
    t = 0
    for v in S:
        if s[t] == v:
            t += 1
        if t == 3:
            break
    if t == 3:
        ans += 1
print(ans)

Measured memory_bytes: 41308
# coding: utf-8
# Your code here!

MAX = 2 ** 15
s = [1] * MAX
s[0] = 0
s[1] = 0

start = 2
while True:
   pmb = 0
   for i in range(start, MAX):
      if s[i] == 1:
         pmb = i
         break
   if pmb == 0:
      break
   
   for i in range(pmb ** 2, MAX, pmb):
      s[i] = 0

   start += 1

while True:
   n = int(input())
   if n == 0: break

   c = 0
   for i in range(2, n // 2 + 1):
      if s[i] == 1 and s[n - i] == 1:
         c += 1

   print(c)


Measured memory_bytes: 5716
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uu unsigned
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define pl pair<ll,ll>
#define mkp make_pair
#define ss second
#define ff first
#define mit(a,b) map<a,b>::iterator
#define sit(a) set<a>::iterator
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define printcas cout<<"Case "<<cas<<": "
#define _ continue;
#define endl '\n'
#define __ cout<<endl;continue;
#define dd (double)
const ll oo=(1ll<<60);
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
double dp[305][305][305]={0};
int main()
{
     //io;
    //string hudai(1000000,'a');
    int T=1;
    //T=gi();
     for(int cas=1;cas<=T;cas++)
    {
        int n,x,cnt[4]={0},i,j,k;
        n=gi();
        for(i=0;i<n;i++)
        {
            x=gi();
            cnt[x]++;
        }
        dp[0][0][0]=0.0;
        for(i=0;i<=cnt[3];i++)
        {
            for(j=0;j<=cnt[2]+cnt[3];j++)
            {
                for(k=0;k<=cnt[1]+cnt[2]+cnt[3];k++)
                {
                    if(i+j+k==0) _
                    dp[i][j][k]=(1.0/(i+j+k+0.0))*(n+0.0+((!i)?0.0:i*1.0*dp[i-1][j+1][k])+((!j)?0.0:j*1.0*dp[i][j-1][k+1])+((!k)?0.0:k*1.0*dp[i][j][k-1]));
                    //if(dp[i][j][k]-n==0.0) cout<<i<<' '<<j<<' '<<k<<endl;
                }
            }
        }
        printf("%.15lf",dp[cnt[3]][cnt[2]][cnt[1]]);


    }
    return 0;
}


Measured memory_bytes: 220624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

ll a[102],MIN[102],MAX[102];

int main() {
	ll n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	ll now=0,j=0;
	bool flag=1;
	for(int i=0;i<n;i++){
		if(now<a[i]){
			MAX[j]=a[i];
			flag=1;
		}
		else{
			if(flag==1){
				flag=0;
				j++;
			}
			MIN[j]=MAX[j]=a[i];
		}
		now=a[i];
	}
	ll ans=0;
	for(int i=0;i<102;i++){
		ans+=MAX[i]-MIN[i];
	}
	cout <<ans;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
V_list = input().split()
C_list = input().split()
dif_list = []
maxim = 0

for i in range(N):
    dif_list.append(int(V_list[i]) - int(C_list[i]))

dif_list.sort(reverse=True)

for i in range(N):
    if dif_list[i]>0:
        maxim += dif_list[i]
    else:
        break;
        
print(maxim)

Measured memory_bytes: 3064
a,b,c= map(int, input().split())

if c >= a+b:
#if float(math.sqrt(a))+ float(math.sqrt(b)) < float(math.sqrt(c)):
    if 4*a*b < (c-a-b)**2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 2940
#include <stdio.h>
#define max 100

int bubbleSort(int*,int);

int main(){
    int n,num[max],count;

    scanf("%d",&n);

    for(int i = 0;i<n;i++){
        scanf("%d",&num[i]);
    }

    count = bubbleSort(num,n);

    for(int i = 0;i < n;i++){
        printf("%d",num[i]);
        if(i < n-1)printf(" ");
    }

    printf("\n%d\n",count);

    return 0;
}

int bubbleSort(int *num,int n){
    int tmp;
    int count = 0;
    int flog = 1;
    int i = 0;

    while(flog){
        flog = 0;
        for(int j = n-1;j > i;j--){
            if(num[j] < num[j-1]){
                tmp = num[j];
                num[j] = num[j-1];
                num[j-1] = tmp;
                count++;
                flog = 1;
            }
        }
        i++;
    }

    return count;
}


Measured memory_bytes: 2140
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val A = nextIntList()
    val m = A.max()!!
    val n = A.sum() - m
    println(if (m==n) "Yes" else "No")
}

Measured memory_bytes: 37924