akhauriyash/Code-Regression huggingface dataset:
n,k,s = gets.chomp.split.map(&:to_i)
ans_array = Array.new(n)
cnt = 0
(0..k-1).each do |i|
  ans_array[i] = s
end
if s != 10**9
  (k..n-1).each do |j|
    ans_array[j] = 10**9
  end
else
  (k..n-1).each do |j|
    ans_array[j] = 10**9 - 1
  end
end
puts ans_array.join(" ")
  



Measured memory_bytes: 4732
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
	ll n,m,ans=0,i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			ans++;
	for(i=1;i<=m;i++)
		for(j=i+1;j<=m;j++)
			ans++;
	printf("%d",ans);
	
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    long long a, b, c;
    long long L, W;
    cin >> a >> b >> c;
    L = 4 * a * b;
    W = a * a + b * b + c * c + 2 * a * b - 2 * a * c - 2 * b * c;
    cout << ( (L < W && (c - a - b > 0)) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
class Max_Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = 0  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i
def main():
    N = int(input())
    *H, = map(int, input().split())
    *A, = map(int, input().split())
    
    dp = Max_Bit(N)
    sort_H_i = sorted((h, i) for i, h in enumerate(H))
    for h, i in sort_H_i:
        dp.update(i+1, dp.get_max(i) + A[i])
    print(dp.get_max())

if __name__ == '__main__':
    main()

Measured memory_bytes: 136764
// review
#include <iostream>

using namespace std;

int n;
string s;

int diff[110];

void solve() {
  int maxDiff = 0;
  diff[0] = 0;
  for (int i=0;i<n;i++) {
    if (s[i] == '(') {
      diff[i+1] = diff[i] + 1;
    } else {
      diff[i+1] = diff[i] - 1;
    }
    maxDiff = max(maxDiff, -diff[i+1]);
  }
  for (int i=0;i<maxDiff;i++) {
    cout << '(';
  }
  cout << s;
  for (int i=0;i<maxDiff + diff[n];i++) {
    cout << ')';
  }
  cout << endl;
}

int main() {
  cin >> n;
  cin >> s;
  solve();
}


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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

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

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

void solve() {
  int N;
  cin >> N;
  cout << (N + 1) / 2 << endl;
  return;
}

signed main() {
  fastio();
  solve();
  // int t; cin >> t; while(t--)solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k,a,b;
  cin>>k>>a>>b;
  bool f=0;
  for(int i=a;i<=b;i++)
    if(i%k==0)
      f=1;
  cout<<(f?"OK":"NG")<<endl;
}


Measured memory_bytes: 3596
using System;

namespace AtCoder
{
    class Class1
    {
        static void Main(string[] args)
        {
            byte A;//年齢
            short B;//金額

            //入力
            string[] input = Console.ReadLine().Split(' ');

            A = byte.Parse(input[0]);
            B = short.Parse(input[1]);

            //13歳
            if (A >= 13)
            {
                Console.WriteLine(B);
            }
            //5歳以下
            else if (A <= 5)
            {
                Console.WriteLine(0);
            }
            //6歳以上12歳以下
            else
            {
                Console.WriteLine(B / 2);
            }
        }

    }
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;

char s[5215];

int main() {
	make2(a, b);
	scanf("%s", s);
	int n = strlen(s);
	if (a + b + 1 != n) {
		cout << "No " << endl;
		return 0;
	}
	if (s[a] != '-') {
		cout << "No " << endl;
		return 0;
	}
	FOR(i,0,a+b+1) {
		if (i == a) continue;
		if (s[i] < '0' || s[i] > '9') {
			cout << "No " << endl;
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}


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

int N, K;

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

    int ans = 1;
    for (int i = 0; i < N; i++) {
        if (ans * 2 < ans + K) ans *= 2;
        else ans += K;
    }

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


Measured memory_bytes: 256
n, m = map(int, input().split())
ps = [int(p)-1 for p in input().split()]
xys = [tuple(int(x)-1 for x in input().split()) for _ in range(m)]

nodes = range(n)
union = {node:node for node in nodes}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

Measured memory_bytes: 33988
import numpy as np
N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]
INF = 10 ** 9


def dfs(i, a, b, c):
    if i == N:
        return abs(A-a) +abs(B-b) + abs(C-c) - 30 if min(a, b, c) > 0 else INF
    Sa = dfs(i+1, a+l[i], b, c) + 10
    Sb = dfs(i+1, a, b+l[i], c) + 10
    Sc = dfs(i+1, a, b, c+l[i]) + 10
    Sx = dfs(i+1, a, b, c) 

    return min(Sa, Sb, Sc, Sx)

print(dfs(0, 0, 0, 0))

Measured memory_bytes: 12500
#include<bits/stdc++.h> 
using namespace std;
const int L = 5000005;
struct point{
	int xx, yy, ww;
}poi[1000005];
struct node{int s, y, w;}edge[L];
long long Fa[L], n, m;
void init(){
    for(int i = 0; i <= n; i++){
    	Fa[i] = i;
	}
}
int Find(int x)
{
    if(Fa[x] == x) return x;
    else return Fa[x] = Find(Fa[x]);
}
void unite(int x,int y)
{
    x = Find(x);
    y = Find(y);
    if(x != y)
    	Fa[y] = x;
}
bool same(int x, int y)
{
    return Find(x) == Find(y);
}
bool cmp(node a, node b)
{
    return a.w < b.w;
}
bool cmp1(point x, point y){
	return x.xx < y.xx;
}
bool cmp2(point x, point y){
	return x.yy < y.yy;
}
int main()
{	
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
    	scanf("%d%d", &poi[i].xx, &poi[i].yy);
    	poi[i].ww = i;
	}
    m = 0;
	sort(poi, poi + n, cmp1);
	for(int i = 0; i < n; i++){
		if(i + 1 < n){
			edge[m].s = poi[i].ww;
			edge[m].y = poi[i + 1].ww;
			edge[m].w = fabs(poi[i].xx - poi[i + 1].xx);
			m++;
		}
		if(i - 1 >= 0){
			edge[m].s = poi[i].ww;
			edge[m].y = poi[i - 1].ww;
			edge[m].w = fabs(poi[i].xx - poi[i - 1].xx);
			m++;
		}
	}
	sort(poi, poi + n, cmp2);
	for(int i = 0; i < n; i++)
        {
		if(i + 1 < n)
                {
			edge[m].s = poi[i].ww;
			edge[m].y = poi[i + 1].ww;
			edge[m].w = fabs(poi[i].yy - poi[i + 1].yy);
			m++;
		}
		if(i - 1 >= 0)
                {
			edge[m].s = poi[i].ww;
			edge[m].y = poi[i - 1].ww;
			edge[m].w = fabs(poi[i].yy - poi[i - 1].yy);
			m++;
		}
	}
	init();
    sort(edge, edge + m, cmp);
   long long su = 0, cnt = 0;
    for(int i = 0; i < m; i++)
    {
        if(cnt == n - 1)			break;
        if(!same(edge[i].s, edge[i].y))
        {
            unite(edge[i].s, edge[i].y);
            su += edge[i].w;
            cnt++;
        }
    }
	printf("%d\n", su);
    return 0;
}

Measured memory_bytes: 11264
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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

  ll N;
  cin >> N;
  vector<ll> A,B,C;
  rep(i,N){
    ll inp ; cin >> inp;
    A.pb(inp);
  }
  rep(i,N){
    ll inp; cin >> inp;
    B.pb(inp);
  }
  rep(i,N){
    ll inp; cin >> inp;
    C.pb(inp);
  }


  sort(all(A)); sort(all(B)); sort(all(C));

  vector<ll> AB,BC;
  rep(i,N){
    AB.pb((lower_bound(all(A),B[i])-A.begin()));
  }
  
  
  rep(i,N){
    if(i==0) continue;
    AB[i]+=AB[i-1];
  }
  
  ll ans = 0;
  rep(i,N){
    ll num = lower_bound(all(B), C[i])-B.begin();
    if(num <= 0) continue;
    ans += AB[num-1];
  }

  cout << ans << endl;
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


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

using namespace std;

int main() {
  int n,A[110];
  cin >> n;

  int mi = 1000;
  int ma = 0;
  for(int i = 0; i < n; i++) {
    cin >> A[i];
    mi = min(mi, A[i]);
    ma = max(ma, A[i]);
  }

  cout << ma - mi << endl;
}

Measured memory_bytes: 3568
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
int main(){
    int i,ans=0,a,b,ten[10]={};
    ten[0]=1;
    for(i=1; i<10; i++){
        ten[i]=ten[i-1]*10;
    }
    scanf("%d %d",&a,&b);
    if(a>b){
        for(i=0; i<a; i++){
            ans+=b*ten[i];
        }
        printf("%d",ans);
        return 0;
    }
    for(i=0; i<b; i++){
        ans+=a*ten[i];
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 1728
a, b, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = min(a) + min(b)
for i in range(m):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)

print(ans)


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

int main()
{
    int N;
    cin>>N;
    char S[N];
    int x=0,max=0;
    for(int j=0;j<N;j++)
    cin>>S[j];
    for(int i=0;i<N;i++)
    {
        if(S[i]=='I')
        x++;
        else
        x--;

        if(x>=max)
        max=x;

    }
    cout<<max;
    return 0;
}


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

int main(){
  int n; cin >>n;
  int cnt1 = 0, cnt2 = 0, cnt4 = 0;
  rep(i,n){
    int a; cin >>a;
    if(a%4==0) cnt4++;
    else if(a%2==0) cnt2++;
    else cnt1++;
  }
  if(cnt2) cnt4--;
  if(cnt1<=cnt4+1) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0; 
}

Measured memory_bytes: 3564
#ABC-128-C
N, M = map(int, input().split())
S = []
ans = 0

for i in range(M):
    ki, *six = map(int, input().split())
    S.append((i, six))

P = list(map(int, input().split()))

for i in range(0, (2**N)):
    confidence = True
    for item in S:
        on_switches = 0
        for switch in item[1]:
            on_switches += i >> (switch-1) & 1
        if on_switches % 2 != P[item[0]]:
            confidence = False
            break
    if confidence == True:
        ans += 1
        
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define pb push_back
#define f first
#define s second
using namespace std;


ll gcd(ll a, ll b)   //Function to find gcd of two numbers
{
    if (a == 0)
    return b;
    return gcd(b % a, a);
}

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

    ll n;
    cin>>n;

    ll arr[n];

    for(int i=0;i<n;i++)
    cin>>arr[i];

    ll sum=0;

    vector<ll>suffix(n);
     
    suffix[n-1] = arr[n-1];

    for(int i=n-2;i>=0;i--)
    {
        suffix[i]= (arr[i]%mod + suffix[i+1]%mod)%mod;
    }

    for(int i=0;i<n-1;i++)
    {
        sum = (sum%mod + (arr[i]%mod * suffix[i+1]%mod)%mod)%mod;
    }

    cout<<sum<<endl;


    return 0;
}

Measured memory_bytes: 6336
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
bool tri(ll a, ll b, ll c)
{
    return (a!=b && b!=c && c!=a &&(a+b>c) && (b+c>a) && (a+c>b));
}
int main()
{
    ll n, i, j, k, testcase,  b ;
    cin >> n;
    ll a[n];
    for(i=0; i<n; i++)
    {
        cin >> a[i];
    }
    b=0;
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            for(k=j+1; k<n; k++)
            {
                if(tri(a[i],a[j],a[k]))
                    b++;
            }
        }
    }
    cout << b ;
    return 0;
}


Measured memory_bytes: 3608
#include<iostream>
using namespace std;
int main(){
  int x1,x2,y1,y2,tx,ty;
  cin >> x1 >> y1 >> x2 >> y2;
  tx = x2-x1;
  ty = y2-y1;
  cout << x2 -ty<<" " << y2 + tx << " "<< x1-ty <<" "<< y1 + tx<<"\n";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;

using namespace std;

vector<vector<int> > g;

void dfs( int curr, int currd, vector<int>& depth )
{
    depth[curr]=currd;

    int i;
    for(i=0; i<(int)g[curr].size(); i++) {
        int next = g[curr][i];
        if(depth[next]<0) {
            dfs(next, currd+1, depth);
        }
    }

    return;
}

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    g.resize(n);
    int i;
    for(i=0; i<n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }
    
    vector<int> depth(n,-1);
    dfs(0, 0, depth);

    int maxid=-1;
    int max=-1;
    for(i=0; i<n; i++) {
        if(depth[i]>max) {
            max=depth[i];
            maxid=i;
        }
    }

    vector<int> depth2(n,-1);
    dfs(maxid, 0, depth2);
    int maxid2=-1;
    int max2=-1;
    for(i=0; i<n; i++) {
        if(depth2[i]>max2) {
            max2=depth2[i];
            maxid2=i;
        }
    }
    if(max2%3==1) {
        printf("Second\n");
    }
    else {
        printf("First\n");
    }

    return 0;
}


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

int dp[1010][20010];

int main(){
    int h,n;
    cin >> h >> n;
    vi a(n+1), b(n+1);
    rep(i,n) cin >> a[i] >> b[i];
    rep(i,1010) rep(j,20010) dp[i][j]=1e9;
    int max_a=*max_element(a.begin(),a.end());

    dp[0][0]=0;
    rep(i,n+1){
        rep(j,h+max_a+1){
            if(i!=0) dp[i][j]=min(dp[i][j],dp[i-1][j]);
            if(j-a[i]>=0) dp[i][j]=min(dp[i][j],dp[i][j-a[i]]+b[i]);
        }
    }

    int ans=1e9;
    for(int i=0;i<max_a+1;i++){
        ans=min(ans,dp[n][h+i]);
    }
    cout << ans << endl;



}

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

using namespace std;

vector< vector<int> >dp(100001, vector<int>(4,-1));
int dfs(vector< vector<int> >&nums, int i, int ac){
    if(i==nums.size()) return 0;
    
    if(dp[i][ac]!=-1) return dp[i][ac];
    
     int taken=0;
         if(ac!=0) taken =  max(taken,dfs(nums,i+1,0) + nums[i][0]);
         if(ac!=1) taken =  max(taken,dfs(nums,i+1,1) + nums[i][1]);
         if(ac!=2) taken =  max(taken,dfs(nums,i+1,2) + nums[i][2]);
      
dp[i][ac]= taken;
    return taken;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin>>n; 
    vector< vector<int> >nums(n, vector<int>(3) );
    dp.assign(100001, vector<int>(4,-1));
    for(int i=0; i<n; ++i) {
        for(int j=0; j<3; ++j)
        cin>>nums[i][j];
    }
    int res= dfs(nums,0,3);
   
    cout<<res<<'\n';
  
    return 0;
}

Measured memory_bytes: 17408
def usirowa(n, x):
    return x*(2*n - x + 1) // 2

n,k = map(int, input().split())

cnt = 0
for i in range(k, n+2):
    cnt += usirowa(n, i) - i*(i - 1) // 2 + 1

print(cnt % (10**9 + 7))

Measured memory_bytes: 9212
use std::io::BufRead;

fn main() {
  let stdin = std::io::stdin();
  for line in stdin.lock().lines() {
    let line = line.unwrap();
    let line = line.trim();
    if line == "0" {
      break;
    }

    let sum = line.as_bytes().iter()
      .map(|x| (x - b'0') as u64)
      .sum::<u64>();
    println!("{}", sum);
  }
}


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

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b) for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n) For(i, 0, n)
#define debug(x) cerr << #x << " = " << (x) << endl;
#define P pair<int,int>
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
const int INF = 100100100;
const int mod = 1e9+7;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//Write From this Line

int main()
{
	//fiel[i][j] = pair(true,false)みたいな…
	while(1){
		int w , h ;
		cin >> w >> h ;
		if(w == 0 && h == 0) break;
		vector<vector<P>> field(h,vector<P> (w));
		rep(i,2*h-1){
			// i / 2行目について、
			if(i % 2 == 0){
				//縦線
				rep(j,w-1){
					cin >> field[i/2][j].second;
				}
			} else {
				//上と下をつなぐところ
				rep(j,w){
					cin >> field[i/2][j].first;
				}
			}
		}
		//fieldが出来たので、h-1,w-1に行くまでの手数を数える
		vector<vector<int>> dist(h,vector<int>(w));
		rep(i,h)rep(j,w) dist[i][j] = INF ;
		queue<P> que;
		auto update = [&](int i, int j, int x){
			if(dist[i][j] != INF) return ;
			dist[i][j] = x;
			que.push(make_pair(i,j));
		};
		update(0,0,1);
		while(!que.empty()){
			int y = que.front().first;
			int x = que.front().second;
			que.pop();
			rep(dir,4){
				int ny = y + dy[dir];
				int nx = x + dx[dir];
				if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
				if(dist[ny][nx] != INF) continue;
				//TODO　移動出来ないときの処理を書く。
				//とりあえず、上から下、左から右に行くと仮定して処理を書く
				//i = 0のとき右に行く
				if(dir==0){
					//右に行けるかどうか/secondを見る
					if(field[y][x].second) continue;
				}
				if(dir == 1){
					//下に行けるかどうか
					if(field[y][x].first) continue;
				}
				if(dir == 2){
					//ひだりにイケるかどうか
					if(field[ny][nx].second) continue;
				}
				if( dir == 3){
					//上に行けるか
					if(field[ny][nx].first) continue;
				}
				update(ny,nx,dist[y][x]+1);
			}
		}
		if(dist[h-1][w-1] == INF){
			cout << 0 << endl;
		}else {
			cout << dist[h-1][w-1] << endl;
		}
	}
} 



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

using namespace std;

int main() {
    int c[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> c[i][j];
        }
    }

    int d[6];
    d[1] = c[0][0];
    d[2] = c[0][1];
    d[3] = c[0][2];
    d[4] = c[1][0];
    d[5] = c[2][0];

    if ((c[1][1] == -d[1] + d[2] + d[4]) &&
        (c[1][2] == -d[1] + d[3] + d[4]) &&
        (c[2][1] == -d[1] + d[2] + d[5]) &&
        (c[2][2] == -d[1] + d[3] + d[5])) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<int> x(m);
    rep(i,m) cin >> x[i];
    sort(all(x));
    if(n >= m) {
        cout << 0 << endl;
        return 0;
    }
    priority_queue<int> q;
    rep(i,m-1) q.push(x[i+1]-x[i]);
    int sum = x[m-1]-x[0];
    rep(i,n-1) {
        int now = q.top();
        q.pop();
        sum -= now;
    }
    cout << sum << endl;
}


Measured memory_bytes: 1276
#include <iostream>
#include <algorithm>
#include <cmath>
#include <functional>
#include <string>
#include <vector>
#include <set>
using namespace std;

#define int long long
#define rep(n, i) for (int i = 0; i < n; i++)
#define rep2(m, n, i) for (int i = m; i < n; i++)
#define rep_r(n, i) for (int i = n - 1; i >= 0; i--)

const int INF = 1LL << 60;
const int MOD = 1e9 + 7;

signed main() {
    int n;
    cin >> n;
    int f[n][5][2];
    int p[n][11];
    rep(n, i) {
        rep(5, j) {
            rep(2, k) {
                cin >> f[i][j][k];
            }
        }
    }
    rep(n, i) {
        rep(11, j) {
            cin >> p[i][j];
        }
    }
    int opt = -INF;
    rep2(1, 1 << 10, bit) {
        int res[n];
        fill(res, res + n, 0);
        rep(n, n_i) {
            rep(10, j) {
                if ((bit & (1 << j)) == 0) continue;
                int k = j / 2;
                int l = j % 2;
                if (f[n_i][k][l]) {
                    res[n_i]++;
                }
            }
        }
        int candidate = 0;
        rep(n, n_i) {
            candidate += p[n_i][res[n_i]];
        }
        opt = max(opt, candidate);
    }
    cout << opt << endl;
    return 0;
}

Measured memory_bytes: 256
n,x,t=map(int, input().split())
a=(n/x)
if a==type(int):
    a=str(a)
    b=int(a[:a.index(".")])
else:
    a=str(a)
    a2=a[a.index("."):]
    if a2=='.0':
        b=int(a[:a.index(".")])
        print(b*t)
    else:
        b=int(a[:a.index(".")])+1
        print(b*t)

Measured memory_bytes: 9200
// Cursor jump numbers
// main @ 39
// global @ 35
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define ll long long int
#define MOD ((int)(1e9) + 7)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  int nc2, mc2;
  if (n < 2) nc2 = 0;
  else 
    nc2 = (n*(n-1))/2;
  if (m < 2) mc2 = 0;
  else mc2 = (m*m - m) /2;
  cout << nc2 + mc2 << '\n';
  return 0;
}


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

void
lowercase(char *s)
{
	int i;
	for (i = 0; s[i] != '\0'; i++)
	{
		s[i] = tolower(s[i]);
	}
}

int
main()
{
	char w[10] = {0};
	char t[1000] = {0};
	scanf("%s", w);
	lowercase(w);

	int n_matches = 0;
	for (;;) {
		scanf("%s", t);

		if (strcmp(t, "END_OF_TEXT") == 0)
			break;

		lowercase(t);
		if (strcmp(t, w) == 0)
			n_matches++;
	}

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

	return 0;
}

Measured memory_bytes: 552
#include <stdio.h>
#include <stdlib.h> // malloc

void insertionSort(int *, int); // N個の要素を含む0-オリジンの配列A

int main() {
  int N, *A, i;
  
  scanf( "%d" , &N );
  A = (int *)malloc(N * sizeof(int));
  for( i=0; i<N; i++ ) scanf( "%d" , &A[i] );
  insertionSort(A, N);
  
  return 0;
}

void insertionSort(int *A, int N) {
  int i, j, k, v;

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



Measured memory_bytes: 2084
def sieve(n)
  primes = Array.new
  primes[0] = 0
  primes[1] = 0
  2.upto(n-1) do |i|
    primes[i] = i;
  end

  i = 2;
  while i*i < n
    if primes[i] != 0
      (i*i).step(n, i) do |j|
        primes[j] = 0
      end
    end
    i = i + 1
  end
  primes
end

primes = sieve(10000)
loop do
  cnt = 0
  data = gets
  if data == nil then break end
  n = data.to_i
  2.upto(n) do |i|
    if primes[i] != 0 && primes[n+1-i] != 0
      cnt = cnt + 1
    end
  end
  puts cnt
end

Measured memory_bytes: 6188
import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (x, y) = br.readLine().split(' ').map { it.toInt() }
    if (x % y == 0) {
        println("-1")

    } else {
        println(x)
    }
}

fun err(print: Any) {
    System.err.println(print)
}

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

using namespace std;

const long long MOD = 1000000007;

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


int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);

    int n;
    cin >> n;

    for(int i = 0; i < n; ++i){
        int j;
        cin >> j;
        if(j & 1 != 0){
            cout << "first";
            return 0;
        }
    }

    cout << "second";

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int ans=0;
  rep1(i,N){
    int c=0;
    int t=i;
    while(1){
      if(t/10==0){
	c++;
	break;
      }
      t/=10;
      c++;
    }
    if(c%2==1) ans++;
  }
  cout << ans << endl;
  
  return 0;
    

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    ll N, X, tmp, cnt = 0, dst = 0;
    cin >> N >> X;
    repi(i, N, 0)
    {
        cin >> tmp;
        dst += tmp;
        cnt++;
        if (dst > X)
        {
            cout << cnt << endl;
            return 0;
        }
    }
    cout << ++cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Al = Counter(A)
    x = list(Al)
    x.sort()

    if len(Al)>3:
        print('No')
    elif len(Al)==3:
        cond1 = (x[0]^x[1]^x[2] == 0)
        cond2 = (Al[x[0]] == N//3) and (Al[x[1]] == N//3) and (Al[x[2]] == N//3)
        if cond1 and cond2:
            print('Yes')
        else:
            print('No')

    elif len(Al)==2:
        cond1 = x[0] == 0
        cond2 = (Al[x[0]] == N//3) and (Al[x[1]] == N - N//3)
        if cond1 and cond2:
            print('Yes')
        else:
            print('No')
    elif len(Al)==1:
        cond1 = x[0] == 0
        cond2 = True
        if cond1 and cond2:
            print('Yes')
        else:
            print('No')

if __name__ == '__main__':
    main()

Measured memory_bytes: 14468
N = int(input())
X, Y, H = [0]*N, [0]*N, [0]*N
for i in range(N):
  X[i], Y[i], H[i] = map(int, input().split())
  
for Cx in range(0, 100+1):
  for Cy in range(0, 100+1):
    H_TOP = 1
    for i in range(N):
      if H[i]:
        H_TOP = H[i] + abs(X[i] - Cx) + abs(Y[i] - Cy)
    ok = True
    for i in range(N):
      if (max(H_TOP - abs(X[i] - Cx) - abs(Y[i] - Cy), 0) != H[i]):
        ok = False
    if ok:
      print(Cx, Cy, H_TOP)

Measured memory_bytes: 3064
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
int n,m,K;
int cost[100][100],tim[100][100];
int main()
{
    while(cin>>n>>m&&(n||m)){
		fill(cost[0],cost[100],1000000);
		fill(tim[0],tim[100],1000000);
		for(int i=0;i<n;i++){
			int a,b,c,t;cin>>a>>b>>c>>t;a--;b--;
			cost[a][b]=cost[b][a]=c;
			tim[a][b]=tim[b][a]=t;
		}
		for(int k=0;k<m;k++)
			for(int i=0;i<m;i++)
				for(int j=0;j<m;j++){
					cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
					tim[i][j]=min(tim[i][j],tim[i][k]+tim[k][j]);
				}
		cin>>K;
		while(K--){
			int p,q,r;
			cin>>p>>q>>r;p--;q--;
			if(r==0)cout<<cost[p][q]<<endl;
			else cout<<tim[p][q]<<endl;
		}
	}
    return 0;
}

Measured memory_bytes: 1236
n=int(input())
s=input()
s="?"+input()
mod=10**9+7

col=[]
for i in range(n):
    if s[i+1]!=s[i]:
        col.append(1)
    else:
        col[-1]+=1
    
for i in range(len(col)):
    now=col[i]
    if i==0:
        ans=3 if now==1 else 6
        continue
    bef=col[i-1]
    if bef==1:
        ans*=2
        ans%=mod
    elif bef==2 and now==2:
        ans*=3
        ans%=mod

print(ans)
        


Measured memory_bytes: 3064
n=int(input())
a=list(map(int,input().split()))
a.sort()

z=a[0]
c=0
ans=0
for i in range(n):
    if z==a[i]:
        c+=1
    else:
        if z==c:
            z=a[i]
            c=1
            continue
        elif z<c:
            ans+=c-z
        elif z>c:
            ans+=c
        z=a[i]
        c=1
p=a.count(a[-1])
if p<a[-1]:
    ans+=p
elif p>a[-1]:
    ans+=p-a[-1]

print(ans)



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

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define SUM(n) ((n)+1)*(n)/2
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7;

using namespace std;
using pii = pair<int,int>;

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

  int n, a, color[10]={};
  cin >> n;
  rep(i,n){
    cin >> a;
    if( a < 3200 ){
      color[ a/400 +1 ] ++;
    } else {
      color[9] ++;
    }
  }
  int sum = 0;
  reps(i,8){
    if( color[i] ){
      sum ++;
    }
  }

  if( sum == 0 ){
    sum ++;
    color[9]--;
  }
  cout << sum << " " << sum + color[9] << '\n';
  return 0;
}


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

int main(){
  string s;
  cin >> s;
  
  int len = s.length();
  int a,z;
  rep(i,len){
    if(s[i]=='A'){
      a = i;
      break;
    }
  }
  rep(i,len){
    if(s[i]=='Z') z = i;
  }
  
  cout << (z-a+1) << endl;
  return 0;
}

Measured memory_bytes: 640
using System;

namespace ABC026A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;

            var word = Console.ReadLine().Split(' ');

            a = int.Parse(word[0]);
            b = int.Parse(word[1]);
            c = int.Parse(word[2]);

            if (a==b && a==c)
                Console.WriteLine(1);

            else if (a!=b && a==c || b!=c && b==a || c!=a && c==b)
                Console.WriteLine(2);

            else
                Console.WriteLine(3);


            Console.ReadKey();
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i,k,n) for(int i = k; i < (int)(n); i++)
using namespace std;
int main(){
        long long N,K;
        cin >> N >> K;
        long long ans = K;
        REP(i,1,N){
                ans*=(K-1);
        }
        cout << ans << endl;

        return 0;
}

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

long long int a,b,c;
string s;

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>a>>s;
	b=(s[0]-'0');
	c=100*b+10*(s[2]-'0')+(s[3]-'0');
	a=a*c;a=a/100;
	cout<<a;
}


Measured memory_bytes: 3592
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int m1,m2,d1,d2; cin>>m1>>d1>>m2>>d2;
    cout<< ((m1 == m2)? 0:1)<<endl;return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
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(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N; cin >> N;
    vec B(N - 1); cin >> B;
    vec A(N, INF);
    REP(i, N - 1){
        Min(A[i], B[i]);
        Min(A[i + 1], B[i]);
    }
    int ans = 0;
    REP(i, N) ans += A[i];
    Out(ans);

    return 0;
}


Measured memory_bytes: 256
import collections

N, K = map(int, input().split())

snacks = collections.defaultdict(int)

for k in range(0, K):
  d = int(input())
  for n in input().split():
    snacks[int(n)] += 1
    
count = 0
for n in range(1, N + 1): 
  if snacks[n] == 0:
    count += 1
   
print(count)

Measured memory_bytes: 9448
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, k;
    cin >> n >> k;
    cout << n - k + 1 << '\n';

}

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

const long long MOD = 1000000007LL;
const long long INF = 1e18;

long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp, long long mod = MOD) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % mod;
       base = base * base % mod;
    }
    return tot;
}
long long slow_mult(long long base, long long exp, long long mod = MOD) {
    long long tot = 0;
    for(;exp > 0;exp >>= 1){
       if((exp & 1) == 1) tot = (tot + base) % mod;
       base = base * 2 % mod;
    }
    return tot;
}

pair<long long, long long> arr[100005];
int used[100005];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    long long k;
    int n; cin >> n >> k;

    for(int i = 0; i < n; ++i)
        cin >> arr[i].second >> arr[i].first;

    sort(arr, arr + n);
    reverse(arr, arr + n);

    priority_queue<pair<long long, int>> pq;
    long long best = 0, cur = 0, dup = 0;

    for(int i = 0; i < k; ++i){

        if(used[arr[i].second] == 0)
            ++dup;
        else
             pq.push(make_pair(-arr[i].first, i));

        cur += arr[i].first;
        ++used[arr[i].second];

    }

    best = max(best, cur + dup * dup);

    //cout << cur << endl;

    for(int i = k; i < n; ++i){

        if(used[arr[i].second] > 0) continue;
        if(pq.empty()) break;

        cur += pq.top().first + arr[i].first;
        pq.pop();
        ++used[arr[i].second];
        ++dup;

        best = max(best, dup * dup + cur);

    }

    cout << best << "\n";

    return 0;
}


Measured memory_bytes: 3320
#include <bits/stdc++.h>
using namespace std;
int n;
void solve()
{
    int i,res=0;
    vector < int > inp(n+2);
    for (i=0;i<n;i++)
        cin>>inp[i];
    inp[n]=0;
    inp[n+1]=0;
    sort(inp.begin(),inp.end());
    if (n%2)
    {
        for (i=n+1;i>=1;i-=2)
            res+=inp[i]-inp[i-1];
    }
    else
    {
        for (i=n+1;i>=0;i-=2)
            res+=inp[i]-inp[i-1];
    }
    cout<<res<<endl;
}
int main()
{
    while(cin>>n)
        solve();
}

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

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

ll A, B, C, x, y, mini;
ll ans;

int main()
{
   // freopen("test.in","r",stdin);

    cin >> A >> B >> C >> x >> y;
    mini = min(x, y);
    x -= mini;
    y -= mini;

    ans = x * min(A, 2LL * C) + y * min(B, 2LL * C) + mini * min(2LL * C, A + B);
    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n;
  int array[100];
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>array[i];
  }
  
  int sum=0;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      sum+=array[i]*array[j];
    }
  }
  
  cout<<sum<<endl;
  return(0);
}

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

long long GetGcd(long long a, long long b) {
    while (a > 0 && b > 0) {
        if (a >= b) {
            a %= b;
        } else {
            b %= a;
        }
    }
    return a + b;
}

void Normalize(long long& a, long long& b) {
    long long g = GetGcd(a, b);
    a /= g;
    b /= g;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long k1 = 1;
    long long k2 = 1;
    for (int i = 0; i < n; ++i) {
        long long t, a;
        cin >> t >> a;

        long long lf1 = k1 / t + (k1 % t != 0);

        long long lf2 = k2 / a + (k2 % a != 0);

        long long l = max(lf1, lf2);

        k1 = l * t;
        k2 = l * a;
    }

    cout << k1 + k2 << endl;

    return 0;
}


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

int main(){
  int n;
  cin>>n;
  vector<int> prime(55556,1);
  prime[0]=0;
  prime[1]=0;
  for(int i=2;i<55556;i++){
    if(prime[i]==1){
      for(int j=i+i;j<55556;j+=i)prime[j]=0;
    }
  }

  int x=0;
  for(int i=2;i<55556;i++){
    if(prime[i]==1&&i%5==1){
      cout<<i;
      x++;
      if(x==n)break;
      cout<<" ";
    }
  }
  cout<<endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> h;
    h.push_back(0);
    rep(i,n) {
        int H;
        cin >> H;
        h.push_back(H);
    }
    h.push_back(0);
    int sum = 0;
    vector<int> tmp;
    rep(i,n+1) {
        if (h[i] == 0 && h[i+1] != 0) tmp.push_back(i+1);
        if (h[i] != 0 && h[i+1] == 0) tmp.push_back(i);
    }
    rep(i,tmp.size()/2) {
        sum += h[tmp[2*i+1]];
        for (int j = tmp[2*i]; j < tmp[2*i+1]; j++) {
            if (h[j] > h[j+1]) {
                sum -= h[j+1];
                sum += h[j];
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())

field = [list(input()) for _ in range(H)]
directions = [[-1, -1], [-1, 0], [-1, 1],
              [0, -1], [0, 1], [1, 0], [1, -1], [1, 1]]
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            bombCnt = 0
            for k in directions:
                if (i + k[0] >= 0 and i + k[0] < H) and (j + k[1] >= 0 and j + k[1] < W):
                    if field[i + k[0]][j + k[1]] == '#':
                        bombCnt += 1
            field[i][j] = str(bombCnt)
for i in range(H):
    print("".join(field[i]))

Measured memory_bytes: 3188
import sys

infty = 10**10

def merge(A,left,mid,right):

	n1 = mid -left
	n2 = right - mid

	L = [0] * n1
	R = [0] * n2

	for i in range(n1):
		L[i] = A[left+i]
	for i in range(n2):
		R[i] = A[mid+i]

	L.append(infty)
	R.append(infty)

	i = 0
	j = 0
	cnt = 0

#	print(f"{left} {mid} {right} {n1} {n2}")
#	print(f"{L} {R}")
	for k in range(left,right):

		cnt += 1

		if L[i] <= R[j]:
			A[k] = L[i]
			i = i + 1
		else:
			A[k] = R[j]
			j = j + 1
		

	return cnt

#	print(A)

def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt

def test():

	n = int(sys.stdin.readline())
	S = list(map(int,sys.stdin.readline().split()))

	result = mergeSort(S,0,n)
	
	for i in range(n-1):
		print(f"{S[i]} ",end='')
	print(S[n-1])
	print(result)


if __name__ == "__main__":
	test()




Measured memory_bytes: 61660
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(void){
    int a,b;
    cin >> a >> b;
    rep(i,1250){
        double s1,s2;
        s1=(double)i*0.08;
        s2=(double)i*0.1;
        if((int)s1==a&&(int)s2==b){
            cout << i << endl;
            return 0;
        } 
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
#ifndef ___Class_Union_Find
#define ___Class_Union_Find

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

class Union_Find
{
private:

	vector<int> data;

public:

	Union_Find(unsigned size_) : data(size_, -1) { }

	void unite(int x, int y);
	
	bool same(int x, int y);

	int root(int x);
};

void Union_Find::unite(int x, int y)
{
	x = root(x);
	y = root(y);

	if (x != y)
	{
		if (data[x] < data[y])
		{
			swap(x, y);
		}

		data[x] += data[y];
		data[y] = x;
	}
}

bool Union_Find::same(int x, int y)
{
	return root(x) == root(y);
}

int Union_Find::root(int x)
{
	return data[x] < 0 ? x : data[x] = root(data[x]);
}

#endif // ___Class_Union_Find


// ------ main ------ //

#include <cstdio>

using namespace std;

int n, q, com, x, y;

int main()
{
	scanf("%d", &n);
	scanf("%d", &q);

	Union_Find u(n);

	for (int i = 0; i < q; i++)
	{
		scanf("%d", &com);
		scanf("%d", &x);
		scanf("%d", &y);

		if (com == 0) { u.unite(x, y); }
		if (com == 1) { printf("%d\n", u.same(x, y) ? 1 : 0); }
	}

	return 0;
}

Measured memory_bytes: 2796