akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(dead_code)]

use std::thread;
use std::io::{ self, Read };
use std::fmt;
use std::iter::Iterator;
use std::cmp::*;
use std::collections::*;
use std::str::*;
use std::mem::*;

#[derive(Default)]
struct Input {
    buf: Vec<String>
}

impl Input {
    fn new() -> Input {
        Input { buf: Vec::new() }
    }

    fn read<T: FromStr>(&mut self) -> T 
    where <T as FromStr>::Err: fmt::Debug {
        self.next().unwrap().parse::<T>().unwrap()
    }

    fn read_2<T: FromStr, U: FromStr>(&mut self) -> (T, U)
    where <T as FromStr>::Err: fmt::Debug,
          <U as FromStr>::Err: fmt::Debug {
        (self.read(), self.read())
    }

    fn read_3<T: FromStr, U: FromStr, V: FromStr>(&mut self) -> (T, U, V)
    where <T as FromStr>::Err: fmt::Debug,
          <U as FromStr>::Err: fmt::Debug,
          <V as FromStr>::Err: fmt::Debug {
        (self.read(), self.read(), self.read())
    }
    fn read_bytes(&mut self) -> Vec<u8> {
        self.next().unwrap().into_bytes()
    }

    fn read_n<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where <T as FromStr>::Err: fmt::Debug {
        let mut v = Vec::new();
        for _ in 0..n { v.push(self.read::<T>()); }
        v
    }
}

impl Iterator for Input {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        while self.buf.is_empty() {
            let mut s = String::new();
            let _res = io::stdin().read_line(&mut s);
            self.buf = s.split_whitespace().map(|s| s.to_owned()).collect::<Vec<_>>();
            self.buf.reverse();
        }
        self.buf.pop()
    }
}

fn run() {
    let mut ip = Input::new();
    let mut c = [[0; 3]; 3];
    for i in 0..3 {
        for j in 0..3 {
            c[i][j] = ip.read();
        }
    }
    'outer: for a0 in -100..101 {
        let mut b = [0; 3];
        for j in 0..3 {
            b[j] = c[0][j] - a0;
        }
        for i in 1..3 {
            let ak = c[i][0] - b[0];
            for j in 1..3 {
                if ak != c[i][j] - b[j] {
                    continue 'outer;
                }
            }
        }
        println!("Yes");
        return;
    }
    println!("No");
}

fn main() {
    let _ = thread::Builder::new()
        .stack_size(10 * 1024 * 1024)
        .spawn(run).unwrap()
        .join();
}

Measured memory_bytes: 8572
#include <stdio.h>

void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
    {
      while ((numbers[right] >= pivot) && (left < right))
	right--;
      if (left != right)
        {
	  numbers[left] = numbers[right];
	  left++;
        }
      while ((numbers[left] <= pivot) && (left < right))
	left++;
      if (left != right)
        {
	  numbers[right] = numbers[left];
	  right--;
        }
    }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}


int main(void)
{
  int n, m, i, j;
  int x[100000];
  int b[100000];
  int sum = 0;

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

  q_sort(x, 0, m - 1);

  for (i = 0; i < m - 1; i++) {
    b[i] = x[i + 1] - x[i];
  }

  q_sort(b, 0, m - 2);

  if (n < m) {
    for (i = 0; i < m - n; i++) {
      sum += b[i];
    }
  }  
  else 
    sum = 0;
  printf("%d\n", sum);
  return 0;
}


Measured memory_bytes: 1408
def main():
    s = list(map(int, input().split()))
    fives = 0
    sevens = 0
    for item in s:
        if item == 5: fives += 1
        if item == 7: sevens += 1
    if fives == 2 and sevens == 1:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int n;
Int ans[220000];

vector<Int> solve(vector<Int> a, vector<Int> b){
    Int hasha = 0, hashb = 0, hashaa = 0;

    Int poyo = 10;//141592;
    Int mod = 998244353;
    Int payo = 1;
    
    for(auto elem:a){
        hasha *= poyo;hasha %= mod;
        hasha += elem;
        hasha %= mod;

        hashaa *= poyo;hashaa %= mod;
        hashaa += 1-elem;
        hashaa %= mod;
    }
    for(auto elem:b){
        hashb *= poyo;hashb %= mod;
        hashb += elem;
        hashb %= mod;
    }

    for(int i = 0;i < b.size();i++){
        payo = poyo * payo;payo %= mod;
    }
    payo += mod - 1;payo %= mod;
    payo = mod - payo;payo %= mod;
    vector<Int> ans(a.size(), -1);
    for(int i = 0;i < b.size();i++){
        if(hasha == hashb)ans[(n-i)%n] = 0;
        if(hashaa == hashb)ans[(n-i)%n] = 1;
        hashb *= poyo;hashb %= mod;
        hashb += payo * b[i] % mod;
        hashb %= mod;
    }
    return ans;
}

int main(){
    cin >> n;
    vector<Int> a(n), b(n), ax(n), bx(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 < 30;i++){
        for(int j = 0;j < n;j++)ax[j] = (a[j] >> i) % 2;
        for(int j = 0;j < n;j++)bx[j] = (b[j] >> i) % 2;
        auto cx =  solve(ax, bx);
        for(int j = 0;j < n;j++){
            if(ans[j] == -1)continue;
            if(cx[j] == -1)ans[j] = -1;
            else ans[j] += cx[j] << i;
        }
        
    }
    for(int i = 0;i < n;i++){
        if(ans[i] == -1)continue;
        cout << i << " " << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 12796
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
  //解説AC
  int main(){
        lint n,m;
        cin>>n>>m;
        map<lint,lint>mp;
        rep(i,m){
            lint a,b;
            cin>>a>>b;
            mp[a]++;
            mp[b]++;
        }
        for(auto x:mp){
            if(x.second%2==1){
                cout<<"NO";
                return 0;
            }
        }
        cout<<"YES";
  }
  
     


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  int nt,na;
  if (C % B == 0) nt = C / B;
  else nt = C / B + 1;
  if (A % D == 0) na = A / D;
  else na = A / D + 1;
  if (nt <= na) cout << "Yes" << endl;
  else cout << "No" << endl; 
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) (long long)((a).size())
const double pi = 3.14159265358979323846;

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
    string s;
    cin>>s;
    for(ll i = 0; i<sz(s); i++)
    {
        if(s[i]=='?') cout<<'D';
        else cout<<s[i];
    }
}


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

int64_t F[200];
string s;

int main()
{
    cin>>s;
    for(int i=0;i<s.size();i++)
        F[s[i]]++;
    int64_t res=int64_t(s.size())*int64_t(s.size()-1)/2+1;
    for(int i='a';i<='z';i++)
        res-=F[i]*(F[i]-1)/2;
    cout<<res;
}


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

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

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;


const int SIZE = 1e5+100;
ll x,y;

int main(){
    cin >> x >> y;

    if(x % y == 0){
          cout << "-1\n";
        return 0;
    }
    

    cout << x*(y-1) << endl;
}

Measured memory_bytes: 256
integer R,G,B,N
integer aka,midori,ao
integer ans
read*,R,G,B,N

ans=0
aka=0
do while(aka*R<=N)
  midori=0
  do while(aka*R+midori*G<=N)
    if(mod(N-aka*R-midori*G,B)==0)ans=ans+1
    midori=midori+1
  end do
  aka=aka+1
end do
print"(I0)",ans
end

Measured memory_bytes: 768
//Daniel Grzegorzewski
#include <bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

const int N = 102;

int n, a, res[N*N][N], x[N];

signed main()
{
    init_ios();
    cin >> n >> a;
    res[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
    	cin >> x[i];
    	for (int j = i; j >= 1; --j)
    		for (int s = n*(a+1); s-x[i] >= 0; --s)
    			res[s][j] += res[s-x[i]][j-1];
    }
    int wyn = 0;
    for (int i = 1; i <= n; ++i)
    	wyn += res[a*i][i];
   	cout<<wyn<<"\n";
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	int h,w;
	cin>>h>>w;
	char c[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>c[i][j];
		}
	}
	for(int k=0;k<h*2;k++){
		cout<<endl;
		for(int l=0;l<w;l++){
			cout<<c[k/2][l];
		}
	}
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

N = int(input())
X = input().split(" ")
ans = []
for i in range(1,101):
    A = 0
    for j in X:
        x = abs(int(j) - int(i)) 
        A += x * x
    ans.append(A)
ans.sort()
print(ans[0])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
#define vi vector<long long>
#define pi pair<long long, long long>
#define mp make_pair
#define endl '\n'
#define _ << ' '
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
#define clog2(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1e9;
const ll N = (1<<5);
const double PI = 3.1415926535897;

int n, k=0, col[100001], a, b;
vector< pair<int, int> > adj[100001];

void dfs(int cur, int p, int pcol){
    int ncol;
    if(pcol==1) ncol = 2;
    else ncol = 1;
    for(auto nxt : adj[cur]){
        if(nxt.F==p) continue;
        if(ncol==pcol) ncol++;
        col[nxt.S] = ncol;
        k = max(k, ncol);
        dfs(nxt.F, cur, ncol);
        ncol++;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("B.txt", "r", stdin);
    #endif
    cin >> n;
    for(int i=0; i<n-1; i++){
        cin >> a >> b;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    dfs(1, -1, -1);
    cout << k << endl;
    for(int i=0; i<n-1; i++) cout << col[i] << endl;
}




Measured memory_bytes: 9344
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define eb emplace_back
#define sz(x) ((int)(x).size())
using namespace std;
ll getmul(ll n){ll int k{0};while(n>0){k+=n%10;n=n/10;}return k;}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     int arr[5];
     int ans{0};
     for(int i=0;i<5;i++){
         cin>>arr[i];
         if(arr[i]==0)
             ans=i+1;
     }
     cout<<ans<<endl;
 return 0;    
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
using ll = long long;
using VI = vector<int>;
Int m[90];
Int lu(Int i){
  if(~m[i]) return m[i];
  if(i>=2) return m[i] = lu(i-1)+lu(i-2);
  if(i==0) return m[i] = 2;
  if(i==1) return m[i] = 1;
}

signed main(){
  memset(m,-1,sizeof(m));
  Int n;
  cin >> n;
  cout << lu(n) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<ll> A(N);
    vector<ll> B(N);
    vector<Pi>BA(N);
    rep(i,N){
        cin>>A[i]>>B[i];
        BA[i] = mp(B[i],A[i]);
    }
    sort(all(BA));
    ll time = 0;
    rep(i,N){
        time+=BA[i].second;
        if(time>BA[i].first){
            cout<<"No"<<endl;
            return 0;
        }

    }



    cout << "Yes" << endl;


    return 0;
    

}

Measured memory_bytes: 9572
#![allow(unused_imports)]
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_end().to_owned()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}
impl<T: Iterator> IteratorExt for T {}


fn main() {
    let (x1, x2, x3, x4, x5) = read!(usize, usize, usize, usize, usize);
    let sum = x1 + x2 + x3 + x4 + x5;
    println!("{}", 1 + 2 + 3 + 4 + 5 - sum);
}

Measured memory_bytes: 2080
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define last          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fr            first
#define sc            second
#define lcm(a,b)      (a*b)/__gcd(a,b)
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
#define endl          '\n'
using namespace std;
int main()
{
     int n;
     cin>>n;
     dom(i,9)
     {
          if(n%i==0 && n/i<10)
          {
               cout << "Yes" << endl;
               return 0;
          }
     }
     cout << "No" << endl;
}


Measured memory_bytes: 3588
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
X = [[] for _ in range(N)]
Z = [set() for _ in range(N)] # NG list
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)
    Z[a-1].add(b-1)
    Z[b-1].add(a-1)
for _ in range(K):
    a, b = map(int, input().split())
    Z[a-1].add(b-1)
    Z[b-1].add(a-1)

def col(n, E):
    C = [-1] * n
    CNT = [0] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        CNT[c] += 1
        while Q:
            x = Q.pop()
            for y in E[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    CNT[C[y]] += 1
                    Q.append(y)
        c += 1
    return C, CNT

C, CNT = col(N, X)
Y = [0] * N
for i in range(N):
    Y[i] = CNT[C[i]] - 1

for i in range(N):
    for j in Z[i]:
        if C[i] == C[j]:
            Y[i] -= 1
    
print(*Y)

Measured memory_bytes: 84648
n, m = map(int, input().split())

friend = [ [] for _ in range(n) ]

for _ in range(m):
    s, t = map(int, input().split())
    friend[s].append(t)
    friend[t].append(s)

flag = [0] * n
group = 0

# def dfs(u):
#    for v in friend[u]:
#        if flag[v] == 0:
#            flag[v] = group
#            dfs(v)

for i in range(n):
    if flag[i] == 0:
        group += 1
        flag[i] = group
        # dfs(i)
        
        stack = [i]
        
        while stack:
            u = stack.pop()
            for v in friend[u]:
                if flag[v] == 0:
                    flag[v] = group
                    stack.append(v)

q = int(input())

for _ in range(q):
    s, t = map(int, input().split())
    if flag[s] == flag[t]:
        print('yes')
    else:
        print('no')



Measured memory_bytes: 23388
#!/usr/bin/env python3

def f(n,a,b):
    if (a + b) % 2:
        return min(a-1,n-b) + 1 + (b-a-1)//2
    else:
        d = b-a
        return d//2

def main():
    N,A,B = map(int,input().split())
    print(f(N,A,B))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func exec(stdin *Stdin, stdout *Stdout) {
	n := stdin.ReadInt()
	k := stdin.ReadInt()
	s := stdin.Read()

	a := []string{}
	for i := 0; i < k; i++ {
		a = append(a, s)
	}
	for i := k; i < n; i++ {
		if s == "1000000000" {
			a = append(a, "1")
		} else {
			a = append(a, "1000000000")
		}
	}

	stdout.Println(strings.Join(a, " "))
}

func main() {
	stdout := NewStdout()
	defer stdout.Flush()
	exec(NewStdin(bufio.ScanWords), stdout)
}

type Stdin struct {
	stdin *bufio.Scanner
}

func NewStdin(split bufio.SplitFunc) *Stdin {
	s := Stdin{bufio.NewScanner(os.Stdin)}
	s.stdin.Split(split)
	s.stdin.Buffer(make([]byte, bufio.MaxScanTokenSize), int(math.MaxInt32))
	return &s
}

func (s *Stdin) Read() string {
	s.stdin.Scan()
	return s.stdin.Text()
}

func (s *Stdin) ReadInt() int {
	n, _ := strconv.Atoi(s.Read())
	return n
}

func (s *Stdin) ReadFloat64() float64 {
	n, _ := strconv.ParseFloat(s.Read(), 64)
	return n
}

type Stdout struct {
	stdout *bufio.Writer
}

func NewStdout() *Stdout {
	return &Stdout{bufio.NewWriter(os.Stdout)}
}

func (s *Stdout) Flush() {
	s.stdout.Flush()
}

func (s *Stdout) Println(a ...interface{}) {
	fmt.Fprintln(s.stdout, a...)
}


Measured memory_bytes: 8064
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		while(true){
			final int H = sc.nextInt();
			final int W = sc.nextInt();
			
			if(H == 0 && W == 0){
				break;
			}
			
			for(int i = 0; i < H; i++){
				for(int j = 0; j < W; j++){
					System.out.print((i + j) % 2 == 0 ? "#" : ".");
				}
				System.out.println();
			}
			System.out.println();
		}
	}

}

Measured memory_bytes: 26844
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;


void print() {
    cout << endl;
}
 
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << ' ';
    print(forward<Tail>(tail)...);
}
 
template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << ' ';
    }
    cout << endl;
}
 
template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}
 


int main(){
  ll n;cin >>n;
  vector<int> l(n);
  int sum = 0;
  for(int i = 0;i < n; i++){
    cin >> l.at(i);
    sum += l.at(i);
  }
  bool ok = true;
  for(int i = 0;i<n; i++)ok &= (sum - l.at(i) > l.at(i));
  
  cout << (ok ? "Yes" : "No" ) << endl;
}


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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int sum = 0;
  for (int i = 1; i <= A; i++) {
    sum++;
    if (i >= K) {
      cout << sum << endl;
      return 0;
    }
  }

  for (int i = A + 1; i <= A + B; i++) {
    if (i >= K) {
      cout << sum << endl;
      return 0;
    }
  }

  for (int i = A + B + 1; i <= A + B + C; i++) {
    sum--;
    if (i >= K) {
      cout << sum << endl;
      return 0;
    }
  }
}

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


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

int main(){
    
    int turn;
    char TARO[101],HANA[101];
    int WIN[3] = {0,0,0};
    scanf("%d",&turn);

    for(int i=0;i<turn;i++){
        scanf("%s",TARO);
        scanf("%s",HANA);
        for(int i=0;i < min(strlen(TARO),strlen(HANA));i++){
            if(TARO[i] < HANA[i]){
                WIN[0]++;
                break;
            }else if(TARO[i] > HANA[i]){
                WIN[1]++;
                break;
            }else if(i == min(strlen(TARO),strlen(HANA))-1 && TARO[i] == HANA[i]){
                if(strlen(TARO) < strlen(HANA)){
                    WIN[0]++;
                }else if(strlen(TARO) > strlen(HANA)){
                    WIN[1]++;
                }else{
                    WIN[2]++;
                }
            }
        }
        //printf("           %d %d %d\n",WIN[0],WIN[1],WIN[2]);
    }

    printf("%d %d\n",WIN[1]*3+WIN[2],WIN[0]*3+WIN[2]);

    


    return 0;
}



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

using namespace std;

int main() {

    long long N, M, A, B, C, D;
    long long ans = 0;
    string S;

    cin >> N >> M;

    cin>>S;

    S[M-1]=S[M-1]-('A'-'a');

    cout << S << endl;
}

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

using namespace std;

// input
int h,w;
char field[52][52];
string query;


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  while(true) {
    cin >> h >> w;
    if(h == 0) break;
    rep(i,h) rep(j,w) cin >> field[i][j];
    cin >> query;
    
    int p_x = 0,p_y = 0;
    int ans = 0;
    rep(i,query.length()) {
      char target = query[i];
      rep(y,h) rep(x,w) {
        if(field[y][x] == target) {
          ans += abs(x-p_x) + abs(y - p_y) + 1;
          p_y = y; p_x = x;
        }
      }
    }
    cout << ans << endl;
  }

}


Measured memory_bytes: 3144
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <iostream>
#include <time.h>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-7
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
//https://codeforces.com/contest/1238/problems
//https://codeforces.com/contest/1238/submit
//w1 b-1
int w[1005][1005];
int b[1005][1005];
int main(){
    int n,k;
    re(w,0);
    re(b,0);
    int x,y;
    char c;
    int cc;

    s(n) s(k)
    int k2 = 2*k;
    for(int i = 0; i < n; i ++){
        s(x) s(y) gc c = gc;
        x %= k2;
        y %= k2;
        if(c == 'B'){
            cc = -1;
        }else if(c == 'W'){
            cc = 1;
        }
        if(x >= k && y >= k){
            x -= k;
            y -= k;
        }else if(x >= k && y < k){
            x -= k;
            cc *= -1;
        }else if(x < k && y >= k){
            y -= k;
            cc *= -1;
        }

        if(cc == 1){
            w[x][y] ++;
        }else if(cc == -1){
            b[x][y] ++;
        }
    }
    for(int i = 1; i < k; i ++){
        w[i][0] = w[i-1][0] + w[i][0];
        w[0][i] = w[0][i-1] + w[0][i];
        b[i][0] = b[i-1][0] + b[i][0];
        b[0][i] = b[0][i-1] + b[0][i];
    }


    for(int i = 1; i < k; i ++){
        for(int j = 1; j < k; j ++){
            w[i][j] = w[i][j] + w[i-1][j] + w[i][j-1] - w[i-1][j-1];
            b[i][j] = b[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
        }
    }
    /*for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            p(w[i][j]) pk
        }
        pn
    }
    pn
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            p(b[i][j]) pk
        }
        pn
    }*/
    int maxi = -1;
    for(int i = 0 ;i < k; i ++){
        for(int j = 0; j < k; j ++){
            x = w[i][j] + b[i][k-1]+b[k-1][j]-b[i][j]-b[i][j]+w[k-1][k-1]-w[k-1][j]-w[i][k-1]+w[i][j];
            y = b[i][j] + w[i][k-1]+w[k-1][j]-w[i][j]-w[i][j]+b[k-1][k-1]-b[k-1][j]-b[i][k-1]+b[i][j];
            maxi = max(max(maxi,x),y);
        }
    }
    p(maxi) pn


    return 0;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    int N;cin>>N;
    vector<int>A(N),B(N),C(N);
    REP(i,N)cin>>A[i];
    REP(i,N)cin>>B[i];
    REP(i,N)cin>>C[i];
    sort(A.begin(),A.end());
    sort(C.begin(),C.end());
    int ans=0;
    REP(i,N){
        int b=B[i];
        auto d=lower_bound(A.begin(),A.end(),b);
        auto e=upper_bound(C.begin(),C.end(),b);
        ans+=(d-A.begin())*(C.end()-e);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_v<T>(ts...)); }
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T1, T2; cin >> T1 >> T2;
	int A1, A2; cin >> A1 >> A2;
	int B1, B2; cin >> B1 >> B2;

	//{
	//	int prev = 0;
	//	int cnt = 0;
	//	int a = 0;
	//	int b = 0;
	//	rep(t, 0, 100000) {
	//		if (t % (T1 + T2) < T1) {
	//			a += A1;
	//			b += B1;
	//		}
	//		else {
	//			a += A2;
	//			b += B2;
	//		}
	//		if (a < b != prev) {
	//			prev = a < b;
	//			cnt++;
	//			dump(cnt);
	//			dump(t, a, b, a < b);
	//		}
	//	}
	//}

	int SA = A1 * T1 + A2 * T2, SB = B1 * T1 + B2 * T2;

	if (SA == SB) {
		cout << "infinity" << endl;
	}
	else {
		if (SB < SA) {
			swap(SB, SA);
			swap(A1, B1);
			swap(A2, B2);
		}
		dump(SA, SB);
		dump(A1, A2);
		dump(B1, B2);

		if (B1 > A1) {
			cout << 0 << endl;
		}
		else {
			int d = SB - SA;
			int a = A1 * T1;
			int b = B1 * T1;
			dump(d, a, b);
			dump(a - b);
			cout << (a - b) / d * 2 + ((a - b) % d != 0) << endl;
		}
	}

	return 0;
}

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

int main() {
  string S;
  cin >> S;

  int max = 0, cnt = 0;
  for(int i = 0; i < 3; ++i){
    if(S.at(i) == 'R'){
      ++cnt;
    }else{
      cnt = 0;
    }
    if(cnt > max) max = cnt;
  }

  cout << max << endl;
}


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

using namespace std;

string s;

int main() {
  cin>>s;
  int n=s.length();
  int i=0, j=n-1, ans=0;
  while (i<j) {
    if (s[i]!=s[j]) ans++;
    i++; j--;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Measured memory_bytes: 55392
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()


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

    pre = A.pop()
    while A:
        a = A.pop()
        pre = gcd(a, pre)
    print(pre)

if __name__ == "__main__":
    main()


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

typedef pair<int,int> pii;
const int N=2e5+5;
int a[N],b[N],p[N],g[N];
int n;
set<pii> st;

int fp(int x){
	if(p[x]==x) return x;
	else return p[x]=fp(p[x]);
}

void lnk(int x,int y){
	x=fp(x);
	y=fp(y);
	if(a[x]<a[y]) p[y]=x;
	else p[x]=y;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x]=y;
		b[i]=x;
	}
	for(int i=1;i<=n;i++){
		while(!st.empty()&&st.begin()->first<a[i]){
			lnk(st.begin()->second,i);
			st.erase(st.begin());
		}
		int x=fp(i);
		st.insert(make_pair(a[x],x));
	}
	for(int i=1;i<=n;i++) g[fp(i)]++;
	for(int i=1;i<=n;i++) printf("%d\n",g[fp(b[i])]);
	return 0;
}

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

int prime(int);

int main(){
  int i,n,a,cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    if(prime(a)==1)cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}
int prime(int x){
  int i;
  if(x<2) return 0;
  if(x==2) return 1;
  else if(x%2==0) return 0;
  for(i=3;i<=sqrt(x);i+=2){
    if(x%i==0) return 0;
  }
  return 1;
}




Measured memory_bytes: 2072
#!/usr/bin/env python3
import sys


def solve(A: int, B: int, N: int):
    # max[A * x // B - A *(x // B)]
    # x <= N
    # x = pB + r -> Ar // B
    r = B-1 if B < N else N - 1 if B == N else N
    ans = (r * A) // B
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9204
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n;
string s[12];
ll a[10];
bool ng[10];
string z;
map<ll, ll> s1[1 << 10], s2[1 << 10];

void dfs(int l, int r, int b, ll sm, map<ll, ll> mp[]){
  if (l == r){
    mp[b][sm]++;
    return;
  }
  rep(i, z.size()){
    if (b >> i & 1) continue;
    if (l == 0 && ng[i]) continue;
    dfs(l + 1, r, b | (1 << i), sm + a[i] * l, mp);
  }
  dfs(l + 1, r, b, sm, mp);
}

int main(){
  while (cin >> n, n){
    memset(a, 0, sizeof(a));
    memset(ng, 0, sizeof(ng));
    z = "";
    rep(i, 1 << 10) s1[i].clear();
    rep(i, 1 << 10) s2[i].clear();

    rep(i, n) cin >> s[i], z += s[i];
    sort(all(z));
    z.erase(unique(all(z)), end(z));
    rep(i, n){
      if (s[i].size() >= 2) ng[lower_bound(all(z), s[i][0]) - begin(z)] = true;
      reverse(all(s[i]));
      ll t = i + 1 < n ? 1 : -1;
      each(c, s[i]){
        a[lower_bound(all(z), c) - begin(z)] += t;
        t *= 10;
      }
    }
    dfs(0, 5, 0, 0, s1);
    dfs(5, 10, 0, 0, s2);
    ll res = 0;
    rep(i, 1 << z.size()){
      each(x, s1[i]) res += x.second * s2[~i & ((1 << z.size()) - 1)][-x.first];
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 13148
package main
import (
  "bufio"
  "fmt"
  // "math"
  "os"
  "strconv"
  "strings"
)

// 行単位で読み込む場合
var sc = bufio.NewScanner(os.Stdin)

func main() {
  sc.Scan()
  H, _ := strconv.Atoi((strings.Split(sc.Text(), " "))[0])
  W, _ := strconv.Atoi((strings.Split(sc.Text(), " "))[1])

  grid := []string{}
  for i := 0; i < H; i++ {
    sc.Scan()
    line := sc.Text()
    addFlag := true
    for j := 0; j < W; j++ {
      if string(line[j]) == "#" {
        break
      }
      if j == W - 1 {
        addFlag = false
      }
    }
    if addFlag {
      grid = append(grid, line)
    }
  }

  for i := 0; i < len(grid[0]); i++ {
    for j := 0; j < len(grid); j++ {
      if string(grid[j][i]) == "#" {
        break
      }
      if j == len(grid) - 1 {
        for k := 0; k < len(grid); k++ {
          if i != len(grid[0]) - 1 {
            grid[k] = grid[k][:i] + "0" + grid[k][i+1:]
          } else {
            grid[k] = grid[k][:i] + "0"
          }
        }
      }
    }
  }

  for _, v := range grid {
    fmt.Println(strings.Join(strings.Split(v, "0"), ""))
  }

}

// 配列中の文字列を全て数値に変換
func arrayAtoi(array []string) []int {
  retarray := []int{}
  for _, v := range array {
    num, e := strconv.Atoi(v)
    if e != nil {
      panic(e)
    }
    retarray = append(retarray, num)
  }
  return retarray
}

// 配列中の最大値を返す
func arrayMax(array []int) int {
  max := array[0]
  for _, v := range array {
    if v > max {
      max = v
    }
  }
  return max
}

// 配列中の最小値を返す
func arrayMin(array []int) int {
  min := array[0]
  for _, v := range array {
    if v < min {
      min = v
    }
  }
  return min
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
using namespace std;
int const INF = 200000000;

int x[110], y[110];
int dp[110][110][110];
int h[110][110];
int main() {
    int n, p; cin >> n >> p;
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    rep(i,0,n) cin >> x[i+1] >> y[i+1];

    repq(i,0,n) {
        h[i][0] = max(0, y[i] - x[i]);
        rep(j,0,i) {
            int cur_x = max(0, x[i] - h[i-1][j-1]);
            h[i][j] = max(0, y[i] - cur_x);
        }
    }
    h[0][0] = h[1][0];

    /*
    rep(i,1,n+1) {
        rep(j,0,i) {
            printf("%d ", h[i][j]);
        }
        cout << endl;
    }
    */

    int ans = -1;
    rep(i,0,110) rep(j,0,110) rep(k,0,110) dp[i][j][k] = INF;

    dp[0][0][0] = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            for(int k=0; k<=j; k++) {
                // printf("check: dp[%d][%d][%d] = %d\n", i, j, k, dp[i][j][k]);
                if(dp[i][j][k] == INF) continue;
                // if(dp[i][j][k] <= p) ans = max(ans, j);
                dp[i+1][j][0] = min(dp[i+1][j][0], dp[i][j][k]);
                dp[i+1][j+1][k+1] = min(dp[i+1][j+1][k+1], dp[i][j][k] + h[i+1][k]);

                // printf("pat1: dp[%d][%d][0] = %d\n", i+1, j, dp[i+1][j][0]);
                // printf("pat2: dp[%d][%d][%d] = %d\n", i+1, j+1, k+1, dp[i+1][j+1][k+1]);
            }
        }
    }

    rep(i,0,110) rep(j,0,110) rep(k,0,110) if(dp[i][j][k] <= p) ans = max(ans, j);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8280
// AUTHOR: ROSHAN SRIVASTAVA
// WEBSITE: https://www.youtube.com/channel/UC6uQdd7kLLOdlHSVklhV7Cw

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int n,k; 
int arr[1009];

int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	cin>>n>>k;
	for(int i =0; i < n; i++)
		cin>>arr[i];
	sort(arr, arr + n);
	int sum = 0;
	for(int i = 0; i < min(n, k); i++) 
		sum += arr[i];
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
	vp v;
	vi va, vb;
	cin >> n >> m;
	REP(i, m)
	{
		ll a, b;
		cin >> a >> b;
		if (a == 1) {
			va.push_back(b);
		} else if (b == n) {
			va.push_back(a);
		}
	}

	sort(ALL(va));

	bool flag = 0;

	REP(i, va.size() - 1)
	{
		if (va[i] == va[i + 1]) {
			flag = 1;
			break;
		}
	}

	if (flag == 1) {
		cout << "POSSIBLE" << endl;
	} else {
		cout << "IMPOSSIBLE" << endl;
	}
}

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

template<class T, class E>
struct SegTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  typedef function<E(E,E)> H;
  typedef function<E(E,int)> P;
  int n;
  F f;
  G g;
  H h;
  P p;
  T d1;
  E d0;
  vector<T> dat;
  vector<E> lazy;
  SegTree(int n_, F f, G g, H h, T d1, E d0, P p=[](E a, int b){ return a; })
    : f(f), g(g), h(h), d1(d1), d0(d0), p(p) {
    n = 1;
    while (n < n_) n *= 2;
    dat.resize(2 * n - 1, d1);
    lazy.resize(2 * n - 1, d0);
  }
  void eval(int k, int l, int r) {
    if (lazy[k] == d0) return;
    dat[k] = g(dat[k], p(lazy[k], r - l));
    if (k < n - 1) {
      lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      lazy[2 * k + 2] = h(lazy[2 * k + 2], lazy[k]);
    }
    lazy[k] = d0;
  }
  void update(int a, int b, E x, int k = 0, int l = 0, int r = -1) {
    if (r == -1) r = n;
    eval(k, l, r);
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      eval(k, l, r);
    }
    else {
      update(a, b, x, 2 * k + 1, l, (l + r) / 2);
      update(a, b, x, 2 * k + 2, (l + r) / 2, r);
      dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  // return op[a..b)
  // k: node id, [l, r): node interval
  E query(int a, int b, int k = 0, int l = 0, int r = -1) {
    // cerr << "a = " << a << ", b = " << b << ", k = " << k << ", l = " << l << ", r = " << r << endl;
    if (r == -1) r = n;
    eval(k, l, r);
    if (r <= a || b <= l) return d1;
    if (a <= l && r <= b) return dat[k];
    E vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
    E vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
    return f(vl, vr);
  }
  void print() {
   int j = 2;
   for (int i = 0; i < 2 * n - 1; i++) {
     cerr << "(" << dat[i] << ", " << lazy[i] << ")";
     if (i == j - 2) { cerr << endl; j *= 2;}
     else { cerr << " "; }
   }
 }
};

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

  int n, q;
  cin >> n >> q;
  SegTree<int, int> seg(
    n,
    [](int a, int b){ return std::max(a, b); },
    [](int a, int b){ return a + b; },
    [](int a, int b){ return a + b; },
    0,
    0);
  rep(i, q) {
    // cerr << "i = " << i << endl;

    int t;
    cin >> t;
    if (t == 0) {
      int a, b, x;
      cin >> a >> b >> x;
      seg.update(a - 1, b, x);
    }
    else {
      int a;
      cin >> a;
      cout << seg.query(a - 1, a) << endl;
    }

    // seg.print();
    // cerr << endl;
  }

  return 0;
}



Measured memory_bytes: 4976
n=int(input())
A=list(map(int,input().split()))

cnt={}
for i in A:
    if i not in cnt:cnt[i]=1
    else:cnt[i] +=1

B={}
C={}
for v,m in cnt.items():
    B[v]=m*(m-1)//2
    C[v]=(m-1)*(m-2)//2

point=sum(B.values())

for i in A:
    print(point-B[i]+C[i])

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

using namespace std;
using ll = long long;
const int MOD = 1e9+7;

std::vector<bool> sieve(size_t N){
    std::vector<bool> IsPrime(N+1);
    for (int i = 2; i <= N; i++)
            IsPrime[i] = true;

        for (int i = 2; i <= N; i++) {
            if (!IsPrime[i]) continue;
            for (int j = 2 * i; j <= N; j += i)
                IsPrime[j] = false;
        }
        return IsPrime;
}
int main(){
    int n;
    vector<bool> f = sieve(123456*2);
    vector<int> ruiseki;
    ruiseki.push_back(0);
    for(int i = 0;i < f.size();i++){
        if(f[i]){
            ruiseki.push_back(ruiseki.back() + 1);
        }else{
            ruiseki.push_back(ruiseki.back());
        }
    }
    while(cin >> n){
        if(n == 0)return 0;
        cout<<ruiseki.at(n*2+1) - ruiseki.at(n+1)<<endl;
    }
}



Measured memory_bytes: 3776
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
double r1, r2;
int main() {
	cin >> r1 >> r2;
	cout << fixed << setprecision(15) << 1.0 / (1.0 / r1 + 1.0 / r2) << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}

class BIT
{
    public:
    vi bit;
    int n;

    BIT(int n) : n(n) , bit(n+1, 0) {
    }

    void add(int i, int val) {
        for (; i <= n; i += i & -i)
            bit[i] += val;
    }
    
    int sum(int i) {
        int ret = 0;
        for (; i >= 1; i -= i & -i)
            ret += bit[i];
        return ret;
    }
};

using t3 = tuple<int,int,int>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q, i;
    cin >> n >> q;
    vi c(n);
    cin >> c;
    vector<t3> qr(q);
    vi ans(q);
    for(i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        l--;r--;
        qr[i] = {r, l, i};
    }
    sort(all(qr));
    BIT B(n);
    vi rpos(n+1, -1);
    i = 0;
    int j = 0;
    while(j < qr.size()){
        int lq,rq,idx;
        tie(rq,lq,idx) = qr[j++];
        while(i <= rq){
            int lst = rpos[c[i]];
            if(lst != -1){
                B.add(lst+1, -1);
            }
            rpos[c[i]] = i;
            B.add(i+1, 1);
            i++;
        }
        ans[idx] = B.sum(rq+1) - B.sum(lq);
    }
    for(i=0;i<q;i++){
        cout << ans[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 17396
#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;
 
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;
 
#define _  %  MOD
#define __ %= MOD
 
#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))
 
#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
#define fbo find_by_order
#define ook order_of_key
 
ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;} // modular exponent
 
int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
	ll n;
	cin>>n;
	ll ans=0;
	vector<ll> a(n+1);
	repA(i,1,n)
	{
		cin>>a[i];
	}	
	ll mx=a[1];
	for(ll i=2;i<=n;i++)
	{
		if(a[i]>=mx)
		{
			mx=a[i];
		}
		else 
		{
			ans+=(mx-a[i]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!



Measured memory_bytes: 4776