akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MOD 998244353
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u % m;
}

long long powMod(long long x, long long n, long long m) {
    long long res = 1;
    while (n > 0) {
        if ((n & 1) == 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int main() {

    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    rep(i,N) cin >> A[i];

    vector<ll> dp(S + 1, 0);
    dp[0] = 1;
    rep(i,N) {
        auto next(dp);
        rep(j,S+1) {
            if (j + A[i] <= S) {
                next[j + A[i]] += dp[j] * modinv(2, MOD);
                next[j + A[i]] %= MOD;
            }
        }
        swap(dp, next);
    }

    cout << dp[S] * powMod(2, N, MOD) % MOD << endl;
    
    return 0;
}

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

#define int long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);

const int N = 2e5;
int gcd_pre[N], gcd_suf[N], arr[N];
signed main () {
	IOS;
	#ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);	 
	// freopen("output.txt", "w", stdout);
	// freopen("errlog.txt", "w", stderr);
	#endif	

	int n; cin >> n;
	gcd_pre[0] = 0, gcd_suf[n + 1] = 0;
	for (int i = 1; i <= n; i += 1) {
		cin >> arr[i];
		gcd_pre[i] = __gcd(gcd_pre[i - 1], arr[i]);
	}
	for (int i = n; i >= 1; i--) {
		gcd_suf[i] = __gcd(gcd_suf[i + 1], arr[i]);
	}
	int mx = -1;
	for (int i = 1; i <= n; i += 1) {
		mx = max(mx, __gcd(gcd_suf[i + 1], gcd_pre[i - 1]));
	}
	cout << mx;
}	

Measured memory_bytes: 3584
x,y=map(int,input().split())
if not((2*x-y)%3==0 and (-x+2*y)%3==0):
  print(0)
  exit()
p=(2*x-y)//3
q=(-x+2*y)//3

def cmb(n,r,mod):
  if r<0 or n<r:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
n=p+q
mod=10**9+7
g1=[1,1]#元table
g2=[1,1]#逆元table
inv=[0,1]#逆元table計算用
for i in range(2,n+1):
  g1.append(g1[-1]*i%mod)
  inv.append(-inv[mod%i]*(mod//i)%mod)
  g2.append(g2[-1]*inv[-1]%mod)

print(cmb(n,p,mod))

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

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

typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;

const int inf=1e9;
const int mod=1e9+7;

vi dp(100110,inf);

int main(){
	int n,k;
	cin>>n>>k;
	int h[n];
	for (int i = 0; i < n; ++i){
		cin>>h[i];
	}

	dp[0]=0;
	for (int i = 0; i < n; ++i){
		for (int j = 1; j <= k; ++j){
			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
		}
	}

	cout<<dp[n-1]<<endl;


	return 0;
}

Measured memory_bytes: 1024
one = {'M':0, 'A':0, 'R':0, 'C':0, 'H':0}
n=int(input())
for i in range(n):
  c=input()[0]
  one[c] = one.get(c,0)+1
m,a,r,c,h=one['M'],one['A'],one['R'],one['C'],one['H']
print(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h)

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

int main()
{long long  T,D;
long long a,b,c;
 cin >> T >> D;
 int count =0;
 c = D*D;
for(int i = 0;i<T;i++)
{
  cin >> a >> b;
 if(a*a + b*b <= c)
 count ++;

}
cout << count ;
}

Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n;
ll a[100010];
int main(){
	scanf("%lld",&n);
	rep(i,0,n)scanf("%lld",a+i);
	ll flag=1,pre=INF;
	for(int i=n-1;i>=0;i--){
		if(a[i]-1>pre)flag=0;
		pre=min(pre,a[i]);
	}
	puts(flag?"Yes":"No");
}

Measured memory_bytes: 896
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n; i++)
        {
            var s = Console.ReadLine().Trim();
            var sL = s.Length;
            var st = 0;
            for (int j = 0; j < sL; j++)
                st += int.Parse(s[j].ToString());
            int p;
            if (st % 9 == 0) p = st / 9 - 1;
            else p = st / 9;
            var ans = sL - 1 + p;
            if (sL == 1) Console.WriteLine("Audrey wins.");
            else Console.WriteLine(ans % 2 == 1 ? "Fabre wins." : "Audrey wins.");
        }
    }
}


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

#define forn(x,n,s) for(int i = x; i < n; i += s )
#define forr(x,n,s) for(int i = x; i>=n; i -= s)

using namespace std;

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

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

int main(){
    go();

    // code here
    int n;cin>>n;
    string arr[n];
    forn(0,n,1) cin>>arr[i];
    unordered_map<string,int> mp;
    forn(0,n,1) mp[arr[i]]++;
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;
}






Measured memory_bytes: 6640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
using namespace std;
struct List{
	char s[30];
};
struct List list;
struct comp{
	bool operator() (const List& a, const List& b) const{
		if(strcmp(a.s,b.s)<0)	return true;
		return false;
	}
};

map <List,int,comp> MAP;
int op[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}},M[10][10],ini[10][10],N,MAX;

bool dfs(int level);

main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	
	int n,i,j,stx,sty,ans,tmpx,tmpy,all,t;
	char ss[10];
	while(scanf(" %d",&N)==1 && N){
		gets(ss);
		memset(ini,0,sizeof(ini));
		for(n=0;n<N;n++){
			gets(ss);
			for(i=0;i<N;i++){
				if(ss[i]=='@')
					ini[n][i] = 2;
				else if(ss[i]=='#')
					ini[n][i] = 1;
			}
		}
		for(MAX=all=0;MAX<=50;MAX++){
			for(i=0;i<N;i++)
				for(j=0;j<N;j++)
					M[i][j] = ini[i][j];
			MAP.clear();
			if(dfs(0)){
				all = 2;
				break;
			}
		}
		if(all==2)
			printf("%d\n",MAX);
		else
			printf("-1\n");
	}
}
bool dfs(int level)
{
	int i,j,stx,sty,tmpx,tmpy,all,t,next[10][10],x,y,k;
	if(level>MAX)
		return false;
	for(i=0;i<30;i++)
		list.s[i] = '\0';
	for(i=all=k=0;i<N;i++){
		for(j=0;j<N;j++){
			if(M[i][j]==1){
				list.s[k++] = '#';
				all++;
			}
			else if(M[i][j]==2){
				stx = i;
				sty = j;
				list.s[k++] = '@';
			}
			else
				list.s[k++] = '.';
		}
	}
	list.s[k++] = level;
	if(all==0)
		return true;
	if(MAP.find(list)!=MAP.end())
		return false;
	MAP[list] = 1;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			next[i][j] = M[i][j];
	for(t=0;t<8;t++){
		tmpx = stx+op[t][0];
		tmpy = sty+op[t][1];
		if(tmpx<0 || tmpx>=N || tmpy<0 || tmpy>=N)
			continue;
		if(next[tmpx][tmpy]==1)
			continue;
		next[tmpx][tmpy] = 2;
		next[stx][sty] = 0;
		for(i=0;i<N;i++){
			for(j=0;j<N;j++){
				if(next[i][j]==2)
					M[i][j] = 2;
				else{
					int tmp = 0;
					for(k=0;k<8;k++){
						x = i+op[k][0];
						y = j+op[k][1];
						if(x<0 || x>=N || y<0 || y>=N)
							continue;
						if(next[x][y]!=0)
							tmp++;
					}
					if(next[i][j]==1){
						if(tmp==2 || tmp==3)
							M[i][j] = 1;
						else
							M[i][j] = 0;
					}
					else{
						if(tmp==3)
							M[i][j] = 1;
						else
							M[i][j] = 0;
					}
				}
			}
		}
		if(dfs(level+1))
			return true;
		next[tmpx][tmpy] = 0;
		next[stx][sty] = 2;
	}
	return false;
}

Measured memory_bytes: 1424
import java.util.*;
import java.io.*;

public class Main {

    static int startWithBlack(String S){
        int N = S.length();
        int ans = 0;
        for(int n=0; n<N; n++){
            if((n%2==0)^(S.charAt(n)=='0')){
                ans++;
            }
        }
        return ans;
    }
    static int startWithWhite(String S){
        int N = S.length();
        int ans = 0;
        for(int n=0; n<N; n++){
            if((n%2==0)^(S.charAt(n)=='1')){
                ans++;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        System.out.println(Math.min(startWithBlack(S), startWithWhite(S)));

    }
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp(a,b) make_pair(a,b)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*y/gcd(x,y);
}

int main(){
	ll S; cin>>S;
    ll i=0;
    while(S>i*i){
        i++;
    }
    //i*iはSよりギリ大きい
    ll r=i,l=i;
    while((r*l-S)>1000000000){
        if(r==l) r--;
        if(r<l) l--;
    }
    //r*l-Sが10^9以下

    printf("0 0 1 %lld %lld %lld",l,r,r*l-S);
}

Measured memory_bytes: 256
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 3010;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;


int n;
char S[N * 2 + 5];
int A[N + 5], B[N + 5];
char F[N * 2 + 5][N * 2 + 5], G[N + 5][N * 2 + 5];
int CntA, CntB;

int main(){
 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
  	for (int i = 1; i <= 2 * n; i++) cin >> S[i];
 	for (int i = 1; i <= n * 2; ++i)
    if (S[i] == 'a') A[++CntA] = i;
    else B[++CntB] = i;
	for (int i = n; i >= 1; --i) {
    	if (A[i] < B[i]) {
    	  F[i][1] = 'a', F[i][2] = 'b';
      	for (int j = i; j <= n; ++j) {
       	 if (j == n || A[j + 1] > B[i]) {
       	   strcpy(F[i] + 3, G[j + 1] + 1);
       	   break;
       	 }
      	}
    } else {
      for (int j = i; j <= n; ++j) {
        if (j == n || B[j + 1] > A[i]) {
          int cnt = 0;
          for (int k = i; k <= j; ++k) F[i][++cnt] = 'b';
          F[i][++cnt] = 'a';
          if (i == j) strcpy(F[i] + cnt + 1, G[i + 1] + 1);
          else strcpy(F[i] + cnt + 1, F[i + 1] + j - i + 1);
          break;
        }
      }
    }
    if (strcmp(F[i] + 1, G[i + 1] + 1) < 0) strcpy(G[i] + 1, G[i + 1] + 1);
    else strcpy(G[i] + 1, F[i] + 1);
  }
    cout << G[1] + 1;
  	return 0;
}


Measured memory_bytes: 36536
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    print(n%k)
    return

#B
def B():

    n = I()
    po = LIR(n)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    if a[0] >= 0:
        print(sum(a)-2*a[0])
        for i in range(1,n-1):
            print(a[0],a[i])
            a[0] -= a[i]
        print(a[n-1],a[0])
    else:
        if a[-1] < 0:
            print(2*a[-1]-sum(a))
            for i in range(n-1):
                print(a[-1],a[i])
                a[-1] -= a[i]
        else:
            m = bisect.bisect_left(a,0)
            p = n-m
            ans = -sum(a[:m])+sum(a[m:])
            print(ans)
            if p > m:
                l = a[-1]
                a = a[:-1]
                a = a[::-1]
                p -= 1
                p,m = m,p
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
                print(l,k)
            else:
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()


Measured memory_bytes: 62368
/*
 * atcoder/abc108_2nd/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * aを決める
 * a % K = 0の場合)  a + b, a + cよりb % K, c % Kである必要がある
 * a % K != 0の場合) b = K - a, c = K - a
 */
int N, K;
ll counter[200100] = {0};
void solve() {
  cin >> N >> K;
  loop(a,1,N+1) {
    counter[a%K]++;
  }

  ll count = 0;
  loop(a,0,K) {
    int bK = ((K-a)+K)%K;
    int cK = ((K-a)+K)%K;
    count += ((bK+cK)%K == 0) * counter[a] * counter[bK] * counter[cK];
  }
  cout << count << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int64_t INF=999999999;

int main() {
   int A,B,C;
   cin>>A>>B>>C;
   vector<int>K={A,B,C};
   sort(K.begin(),K.end());
   cout<<10*K[2]+K[1]+K[0]<<endl;
return 0;}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    long long now, back, backback;
    if(n == 0 || n == 1) {
        cout << 0 << endl;
        return 0;
    }

    now = 1;
    long long count = 0;
    long long result = 0;
    if(n%2==0) {
    //    for(int i = 1;i < n;i = i*5) {
    //        count += n/i/2;
    //    }
        count = n/5/2;
        result = count;
        while(count > 0) {
            count = count/5;
            result+=count;
        }
    } else {
        cout << 0 << endl;
        return 0; 
    }


    cout << result << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
   int A,B;
   string S,T,U;
   cin>>S>>T;
   cin>>A>>B;
   cin>>U;
   //cout<<x<<y<<i;
    if (U == S) {  A = A - 1;}
    else {

        B = B - 1;
    }
    cout<<A<<' '<<B;
}

Measured memory_bytes: 256
#include <iostream>
#define nmax 1005
#define mod 1000000007
using namespace std;
char s[nmax][nmax];
int h, w;
int dp[nmax][nmax];

int main()
{
    int i, j;
    cin >> h >> w;
    for (i = 1; i <= h; i++)
        cin >> (s[i] + 1);

    dp[1][1] = 1;
    s[1][1] = '#';

    for (i = 1; i <= h; i++)
        for (j = 1; j <= w; j++)
            if (s[i][j] == '.')

                dp[i][j] = (1LL * dp[i - 1][j] + dp[i][j - 1]) % mod;

    cout << dp[h][w] << '\n';

    return 0;
}


Measured memory_bytes: 5120
#include<stdio.h>
#include<string.h>
#define LEN 100000


typedef struct pp{
  char name[10]; //??????
  int t; //?????????????????????
}P;

void enqueue(P);
P dequeue(void);
void initialize(void);
int isEmpty(void);
int isFull(void);

P Q[LEN+1];
int head, tail, n;

int main(){
  int elaps = 0, c;
  int i, q; //q:???????????????
  P u;
  scanf("%d %d", &n, &q);

  initialize();

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }

  head = 1;
  tail = n+1;

  while(1){
    if(isEmpty()) break;

    u=dequeue();

    if(u.t > q ){
      elaps +=q;
      u.t -= q;
      enqueue(u); 
    }
    else {
      elaps +=u.t;
      printf("%s %d\n",u.name,elaps);
    }

  }

  return 0;
}


void initialize(void){
  head = tail = 0;
}

int isEmpty(void){
  return head == tail;
}

int isFull(void){
  return head == (tail + 1) % LEN;
}

void enqueue(P x){ /* ?????\??????????°????????´? x ????????????????????? */
  if(isFull()) fprintf(stderr,"overflow\n");
  Q[tail] = x;
  if (tail + 1 == LEN) tail = 0;
  else tail++;
}

P dequeue(void){ /* ?????\??????????????????????´????????????????????????? */
  P x;
  if(isEmpty()) fprintf(stderr,"underflow\n");
  x = Q[head];
  if (head + 1 == LEN) head = 0;
  else head++;
  return x;
}

Measured memory_bytes: 2160
#include<stdio.h>
int main(void)
{
	int a, b,x, y, z;
	scanf("%d %d", &a, &b);
	
	x = a + b;
	y = a - b;
	z = a * b;

	if (x >= y&& y >= z || x>=z&&z>=y)
		printf("%d", x);
	else {
		if (y >= x && x >= z || y>=z&&z>=x)
			printf("%d", y);


		else {
			if (z >= x && x >= y || z>=y&&y>=x)
				printf("%d", z);
		}
	}


	return 0;
}

Measured memory_bytes: 128
const main = (input: void) => {
  const a: number = input.split(' ')[0];
  const b: number = input.split(' ')[1];

  if ( (a*b) % 2 === 0 ) {
    console.log('Even');
  } else {
    console.log('Odd');
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()

Measured memory_bytes: 18244
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010000;
ll fac[N],fnv[N];
int n,m;

int main() {
	fac[0]=fnv[0]=1;
	for (int i=1;i<=1000000;i++) {
		fac[i]=fac[i-1]*i%mod;
		fnv[i]=fnv[i-1]*powmod(i,mod-2)%mod;
	}
	scanf("%d%d",&n,&m);
	if (n>m) swap(n,m);
	ll ans=0;
	for (int i=0;i<=n;i++) {
		ans=(ans+powmod(mod-1,i)*powmod(n+1,m-i)%mod*powmod(m+1,n-i)%mod*
			fac[m]%mod*fnv[m-i]%mod*fac[n]%mod*fnv[n-i]%mod*fnv[i])%mod;
//		printf("%d %lld\n",i,powmod(mod-1,i)*powmod(n+1,m-i)%mod*powmod(m+1,n-i)%mod*
//			fac[m]%mod*fnv[m-i]%mod*fac[n]%mod*fnv[n-i]%mod*fnv[i]%mod);

	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 16000
import sys
def evaluate(s):
    a,op,b = s.split()
    a=int(a)
    b=int(b)
    if op=='+':
        return a+b
    if op=='-':
        return a-b
    if op=='*':
        return a*b
    if op=='/':
        return a//b
    if op=='?':
        sys.exit(0)

while True:
    s =input()
    print(evaluate(s))
    


Measured memory_bytes: 5600
#include<ctime> 
#include<cmath> 
#include<cstdio>  
#include<cstring> 
#include<algorithm>
#define gc getchar() 
#define pc putchar 
#define rep for(a,b,c) for(int a = b;a <= c;++ a) 
#define per for(a,b,c) for(int a = b;a >= c;-- a) 
inline int read() { 
	 int x = 0,f = 1; 
	 char c = gc; 
	 while(c < '0' || c > '9') c = gc; 
	 while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc; 
	 return x * f; 
} 
void print(int x) {
	if(x < 0) { 
		pc('-'); 
		x = -x; 
	} 
	if(x >= 10) print(x / 10); 
	pc(x % 10 + '0'); 
} 
const int maxn = 1000007; 
bool solve() { 
	static int a[maxn]; 
	int n = read(); 
	int mx = 0,mn = 0x3f3f3f3f; 
	for(int i = 1;i <= n;++ i)  { 
		a[i] = read(); 
		mx = std::max(mx,a[i]); 
		mn = std::min(mn,a[i]); 
	}  
	if(mx - mn >= 2) return true; 
//	if(mx == n - 1 && mn != n - 1) return true; 
	int c1 = 0,c2 = 0; 
	for(int i = 1;i <= n;++ i) { 
		if(a[i] == mx) c1 ++; 
		else c2 ++ ;
	} 
	int sum = mx; 
	if(mx != mn) {   
		int res = sum - c2; 
		if(res <= 0) return true; 
		if(c1 < res * 2) return true; 
	} 
	if(mx == mn) { 
		sum ++; 
		if(mx == n - 1) return false; 
		if(mx * 2 > n) { 
			return true; 
		} 
	} 
	return false;
	
} 
int main() { 
		puts(solve() ? "No" : "Yes");  
} 
/*
3
3
1 2 2
3
1 1 2
5
4 3 4 3 4
*/


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i = 0; i < (n); ++i)
typedef long long ll;


int main(void) {
  double N;
  cin >> N;
  double a=0.0;
  for(int i = 1; i <= N; ++i) {
    if(i % 2 != 0) ++a;
  }

  printf("%.10f\n", a/N);


  return 0;
}


Measured memory_bytes: 256
//writer：Sakura
//problem：
//id：
//from：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
//#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int k;
int a,b,c;

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d %d %d %d",&a,&b,&c,&k);
	int tmp=max(a,max(b,c));
	if(tmp==a){
		tmp=0;
		for(int i=1;i<=k;i++){
			a*=2;
		}
	}
	if(tmp==b){
		tmp=0;
		for(int i=1;i<=k;i++){
			b*=2;
		}
	}
	if(tmp==c){
		tmp=0;
		for(int i=1;i<=k;i++){
			c*=2;
			tmp+=c;
		}
	}
	tmp=a+b+c;
	printf("%d\n",tmp);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
using namespace std; using ll=long long; using P=pair<int,int>;
const int INF=1e9; template<typename T> using vec=vector<T>;
ll ke(ll x) {ll res=0; while(x>0) res+=x%10, x/=10; return res;}
int main() {
  int n,m; cin>>n>>m;
  vec<int> p={-1,2,5,5,4,5,6,3,7,6};
  vec<char> c={'-','1','2','3','4','5','6','7','8','9'};
  vec<int> v(m);
  for(int i=0;i<m;i++) cin>>v[i];
  vec<string> s(n+1); s[0]="";
  auto pred = [](string a, string b) {if (a.size()!=b.size()) return a.size()<b.size(); else return a<b;};
  for(int i=0;i<=n;i++) {
    string nx=s[i];
    if (i != 0 && s[i].empty()) continue;
    for(int j:v) {
      int mc=i+p[j];
      if (mc<=n) s[mc]=max(s[mc], s[i]+c[j], pred);
    }
    if (i!=0) s[i-1].clear();
  }
  //for(int i=0;i<=n;i++) cout<<i<<": "<<s[i]<<endl;
  cout<<s[n]<<endl;
}

Measured memory_bytes: 43648
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define INF -1000000000

using namespace std;

int N;

vector<double> v;
double dp[3000][3000];
double solve(int id,int count){
	if(id >= N){
		if(count < (N/2)+1){
			return 0.0;
		}
		return 1.0;
	}
	if(dp[id][count] > -1.0) return dp[id][count];
	dp[id][count] = solve(id+1,count)*(1-v[id]);
	dp[id][count] += solve(id+1,count+1)*(v[id]);
	return dp[id][count];
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> N;
	double a;
	for (int i = 0; i < N; ++i){
		cin >> a;
		v.push_back(a);
	}

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

	printf("%.10f", solve(0,0));

	return 0;
}

Measured memory_bytes: 70784
#include <iostream>
#include <math.h>
#include <set>

using namespace std;

typedef long long ll;

#define REP(i, n) for (ll i = 0; i < n; ++i)
#define FOR(i, n, m) for (ll i = (n); i < (m); ++i)

const int MOD = 1000000007;

const int MAX = 2e5+10;

ll fac[MAX];  /// fac[n] = n!
ll finv[MAX]; /// (fac[n] * finv[n]) % MOD = 1
ll inv[MAX];  /// (n * inv[n]) % MOD = 1

void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  FOR (i, 2, MAX) {
    fac[i] = fac[i-1]*i % MOD;
    inv[i] = MOD - inv[MOD%i]*(MOD/i) % MOD;
    finv[i] = finv[i-1]*inv[i] % MOD;
  }
}

ll nCk (int n, int k) {
  if (n < k || k < 0 || n < 0) return 0;
  return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}

ll nHk (int n, int k) {
  return nCk(n-1+k, n-1);
}

int N;
ll B[MAX];

int main() {

  init();

  cin >> N;
  REP (i, N) {
    int a;
    cin >> a;
    B[a-1] = i+1;
  }

  set<int> right, left;
  left.insert(0);
  right.insert(N+1);

  ll ans = 0;
  REP (i, N) {
    int k = B[i];
    int l = *(prev(left.lower_bound(k),1));
    int r = *right.upper_bound(k)-1;
    ans += (i+1)*(k-l)*(r-k+1);
    right.insert(k);
    left.insert(k);
  }

  cout << ans << endl;
  return 0;

}

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

#define int long long
#define REP(i,n) for(int i=0;i<n;i++)

int q,a,b;

int solve(){
    int s=sqrt(a*b);
    int r=s*2-2;
    if(s*(s+1)<a*b)r+=1;
    if(s*s==a*b&&a!=b)r-=1;
    return r;
}

signed main(void){
    cin>>q;
    REP(i,q){
        cin>>a>>b;
        cout<<solve()<<endl;
    }
}


Measured memory_bytes: 256
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }
    val pair = list.indices.map { Pair(it, list[it]) }.sortedBy { it.second }.map { it.first + 1 }
    println(pair.joinToString(" "))

}

Measured memory_bytes: 84664
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> prl;
typedef vector<ll> vcl;
typedef map<ll,ll> mapl;
typedef unordered_map<ll,ll> umap;
#define pb push_back
#define all(v) v.begin(), v.end()
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repi(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;
    ll R,C,K,r[200005],c[200005],v[200005];
    ll dp[3005][3005][5]={0},ans=0;
    ll vs[3005][3005]={0};
int main() {
    // your code goes here
    cin >> R >> C >> K;
    rep(i,1,K){
    	cin >> r[i] >> c[i] >> v[i];
    	vs[r[i]][c[i]]=v[i];
    }
    rep(i,1,R){
    	rep(j,1,C){
    		rep(k,0,3){
    			if(k==0){
    				chmax(dp[i][j][k],dp[i][j-1][k]);
    				chmax(dp[i][j][k],dp[i-1][j][0]);
    				chmax(dp[i][j][k],dp[i-1][j][1]);
    				chmax(dp[i][j][k],dp[i-1][j][2]);
    				chmax(dp[i][j][k],dp[i-1][j][3]);
    			} else if(vs[i][j]==0) {
    				chmax(dp[i][j][k],dp[i][j-1][k]);
    			} else if(k!=1) {
    				chmax(dp[i][j][k],dp[i][j-1][k]);
    				chmax(dp[i][j][k],dp[i][j-1][k-1]+vs[i][j]);
    			} else {
    				chmax(dp[i][j][k],dp[i][j-1][k]);
    				chmax(dp[i][j][k],dp[i][j-1][k-1]+vs[i][j]);
    				chmax(dp[i][j][k],dp[i-1][j][0]+vs[i][j]);
    				chmax(dp[i][j][k],dp[i-1][j][1]+vs[i][j]);
    				chmax(dp[i][j][k],dp[i-1][j][2]+vs[i][j]);
    				chmax(dp[i][j][k],dp[i-1][j][3]+vs[i][j]);
    			}
    		}
    	}
    }
    chmax(ans,dp[R][C][0]);
    chmax(ans,dp[R][C][1]);
    chmax(ans,dp[R][C][2]);
    chmax(ans,dp[R][C][3]);
    cout << ans << endl;
    return 0;
}


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

using namespace std;


int main() {
    string s;
    cin >> s;
    auto f = [&](char c) {
        return count(s.begin(), s.end(), c) != 0;
    };

    if ((f('E') ^ f('W')) || (f('N')^f('S'))){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


S = readline().rstrip().decode('utf-8')

N = len(S)+1

from_left = [0]*N
from_right = [0]*N

for i,s in enumerate(S,1):
  if s == '>':
    from_left[i] = 0
  else:
    from_left[i] = from_left[i-1]+1
    
for i,s in enumerate(S[::-1]):
  i = N-2-i
  if s == '<':
    from_right[i] = 0
  else:
    from_right[i] = from_right[i+1]+1
    
seq = [x if x>y else y for x,y in zip(from_left, from_right)]

answer = sum(seq)
print(answer)

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

int main()
{
	int nNum=0;
	cin>>nNum;
	int nIn[3]={0};
	while(nNum--)
	{
		cin>>nIn[0]>>nIn[1]>>nIn[2];
		int nMax=max(max(nIn[0],nIn[1]),nIn[2]);
		if(nMax*nMax*2==nIn[0]*nIn[0]+nIn[1]*nIn[1]+nIn[2]*nIn[2])
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3008
import java.util.Scanner;

class Main {

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

        int W = scan.nextInt();
        int H = scan.nextInt();
        int C = scan.nextInt();
        int a = W;
        int b = H;
        int c;

        while (a % b != 0) {
            c = a;
            a = b;
            b = c % a;
        }
        System.out.println((W / b) * (H / b) * C);
    }
}



Measured memory_bytes: 26096
#include<iostream>
#include<map>

using namespace std;

int main(){
    int N;
    cin >> N;
    map<int,int> mp;
    int tmp;
    for(int i=1;i<N+1;i++){
        cin >> tmp;
        mp[tmp]=i;
    }
    for(int i=1;i<N;i++){
        printf("%d ",mp[i]);
    }
    printf("%d\n",mp[N]);
}

Measured memory_bytes: 5504
use std::io::{BufRead, Write};

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    let mut reader = std::io::BufReader::new(stdin.lock());
    let mut writer = std::io::BufWriter::new(stdout.lock());

    let (a, v): (i64, i64) = {
        let mut buf = String::new();
        reader.read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };

    let (b, w): (i64, i64) = {
        let mut buf = String::new();
        reader.read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };

    let t: i64 = {
        let mut buf = String::new();
        reader.read_line(&mut buf).unwrap();
        buf.trim_end().parse().unwrap()
    };

    if v <= w {
        writeln!(writer, "NO").unwrap();
    } else {
        if ((a - b).abs() + (v - w) - 1) / (v - w) <= t {
            writeln!(writer, "YES").unwrap();
        } else {
            writeln!(writer, "NO").unwrap();
        }
    }
}

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

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

using namespace std;

/////////////////////////////////////////////////////
ll N,M,A[111][111], B[111], C;
ll ans;
ll i, j,k,l;

int main(){
    scanf("%lld%lld%lld", &N,&M,&C);
    fornum(i,0,M){
        scanf("%lld", &B[i]);
    }
    fornum(i,0,N){
        ll sc = 0;
        fornum(j,0,M){
            ll a;
            scanf("%lld", &a);
            sc += a * B[j];
        }
        sc += C;
        if(sc>0){
            ans++;
        }
    }
    printf("%lld",ans);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


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

  int zeros=0, ones=0;
  REP(i, s.size()){
    if(s[i]=='0') ++zeros;
    else ++ones;
  }
  cout<<2*min(zeros, ones)<<endl;
  return 0;
}


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

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
using ll = long long;

void solve();

int main(void){
    string s;
    cin >> s;
    int lens = s.length();
    for(int i = 0; i <= lens-2; i++){
        if(s[i] == s[i+1]){
            cout << i+1 << " " << i+2 << endl;
            return 0;
        }
    }

    for(int i = 0; i <= lens-3; i++){
        if(s[i] == s[i+2]){
            cout << i+1 << " " << i+3 << endl;
            return 0;
        }
    }

    cout << -1 << " " << -1 << endl;
    return 0;
}

void solve(){}

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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int x, a, b;
    cin >> x >> a >> b;
    if(abs(x-a) > abs(x-b) ) cout << 'B' << endl;
    else cout << 'A' << endl; 
}

Measured memory_bytes: 256
N = int(input())
r = [int(input()) for i in range(N)]

tmp_max = r[1] - r[0]
tmp_min = r[0]

for i in range(N-1):
  if(r[i+1] - tmp_min > tmp_max):
    tmp_max = r[i+1] - tmp_min
  if(r[i+1] < tmp_min):
    tmp_min = r[i+1]

print(tmp_max)
    



Measured memory_bytes: 13596
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <map>
#include <algorithm>
#include <functional>


int main()
{
	int N = 0, ans = 0;
	double ave = 0;

	std::cin >> N;

	std::vector<int>X(N);

	for (int i = 0; i < N; i++)
	{
		std::cin >> X[i];
		ave += (double)X[i] / (double)N;
	}

	int P = (int)round(ave);
	for (int i = 0; i < N; i++)
	{
		ans += (X[i] - P) *  (X[i] - P);
	}


	std::cout << ans << std::endl;

	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        for (int i = 0 ; i < s.length() ; i++) {
            for (int j = 0 ; j < s.length() ; j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) {
                   System.out.println("no");
                   return;
                }
            }
        }
        System.out.println("yes");
    }

}

Measured memory_bytes: 20820
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <iomanip>
using namespace std;
#define Would
#define you
const int INF = 999999999;
const int MOD = 1e9 + 7;

long long n, m, k[100005], dp[100005];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) { cin >> k[i]; }
	memset(dp, 9999, sizeof(dp));
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= i + m; ++j) {
			dp[j] = min(dp[j], dp[i] + abs(k[i] - k[j]));
		}
	}
	cout << dp[n - 1] << endl;
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N;
    string S;
    cin >> N >> S;
    using bs = bitset<26>;
    vector<bs> dvs_l(N + 1), dvs_r(N + 1);
    for (ll i = 0; i < N; i++) {
        bs t;
        t[S[i] - 'a'] = true;
        dvs_l[i + 1] = dvs_l[i] | t;
    }
    for (ll i = 0; i < N; i++) {
        bs t;
        t[S[N - 1 - i] - 'a'] = true;
        dvs_r[N - 1 - i] = dvs_r[N - i] | t;
    }

    ll ans = -L_INF;
    for (ll i = 0; i <= N; i++) {
        bs t = dvs_l[i] & dvs_r[i];
        ans = max(ans, (ll)t.count());
    }

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

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 256
program j01;
type xx=record id:longint;w:int64; end;
var a:array[0..100086]of xx;
    n,i,last,pre:longint;
    sum:int64;
    ans:array[0..100086]of int64;

function cmp(a,b:xx):boolean;
begin
  if a.w<>b.w then exit(a.w>b.w) else exit(a.id>b.id);
end;

procedure sort(l,r:longint);
var i,j:longint;x,y:xx;
begin
  i:=l;j:=r;x:=a[(i+j)div 2];
  repeat
    while cmp(a[i],x) do inc(i);
    while cmp(x,a[j]) do dec(j);
    if i<=j then
    begin
      y:=a[i];a[i]:=a[j];a[j]:=y;
      inc(i);dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    read(a[i].w);a[i].id:=i;
  end;
  sort(1,n);sum:=0;pre:=n+1;
  for i:=1 to n do
  begin
    if a[i].id<pre then
    begin
      ans[pre]:=sum-a[i].w*(i-1);
      sum:=a[i].w*(i-1);pre:=a[i].id;
    end;
    inc(sum,a[i].w);
  end;
  inc(ans[pre],sum);
  for i:=1 to n do writeln(ans[i]);
end.


Measured memory_bytes: 3328
def f(a)
  g = lambda{|a, positivep|
    total = sum = 0
    r = []
    a.each{|curr|
      if positivep
        r << new_curr = [curr, -sum-1].min
        sum += new_curr
        total += curr - new_curr
      else
        r << new_curr = [curr, -sum+1].max
        sum += new_curr
        total += new_curr - curr
      end
      positivep = !positivep
    }
    # p r
    total += 1 if sum == 0
    total
  }
  [g.(a, true), g.(a, false)].min
end

N = gets.to_i
A = gets.split.take(N).map(&:to_i)
p f(A)


Measured memory_bytes: 13060
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int h, w, k, i, j, a, b, q;
	cin >> h >> w >> k;
	vector<pair<int, int>> d(h * w + 1);
	vector<int> cost(h * w + 1, 0);
	for (j = 0; j < h; j++) {
		for (i = 0; i < w; i++) {
			scanf("%d", &a);
			d[a] = make_pair(i, j);
		}
	}
	for (i = 1 + k, j = 1; i <= h * w; i++, j++)
		cost[i] = cost[j] + abs(d[i].first - d[j].first) + abs(d[i].second - d[j].second);
	cin >> q;
	for (i = 0; i < q; i++) {
		scanf("%d%d", &a, &b);
		printf("%d\n", cost[b] - cost[a]);
	}
	return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N,K;
    Scd(N);

    vl a(N);
    vl s(N+1,0);
    Rep(i,N){
        Scll(a[i]);
        s[i+1] += s[i] + a[i];
    }

    sort(s.begin(),s.end());

    ll tmp = s[0];
    ll cnt = 1;
    ll ans = 0;

    Repe(i,N+1,1){
        // printf("%lld\n", s[i] );
        if( tmp == s[i] ) cnt++;
        else ans += cnt*(cnt-1)/2 , tmp = s[i] , cnt = 1;
    }
    if( cnt ) ans += cnt*(cnt-1)/2;

    printf ("%lld\n", ans );

    return 0;
}



Measured memory_bytes: 3328
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<cassert>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<limits>
#include<ctime>
#include<stack>
#include<bits/stdc++.h>
#define long long
using namespace std;

int main(){
	int a,b;
	cin>>a>>b;
	int ans=b;
	for(int i=0;i<a-1;i++){
		ans*=(b-1);
	}
	cout<<ans;
}


Measured memory_bytes: 3588
{-# LANGUAGE FlexibleContexts #-}

module Main where

-- import Debug.Trace
import Data.List
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Word
import Data.Char
import Data.Bits
import Data.Array
-- import Data.Array.Unboxed
-- import Data.Array.IO
import Data.Maybe
-- import qualified Data.Map as M
import qualified Data.IntMap as M
-- import Control.Monad.ST
-- import Data.STRef
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

size = 3
maxAdr = size*size -1

solver :: [[Int]] -> Int
solver lst = bfs start goalID where
    bfs start goalID = iter ((Seq.singleton (start, generateID start, 0)), M.empty) where
        iter (que, visited) = case Seq.viewr que of
            Seq.EmptyR -> error "No path found."
            que Seq.:> path@(b, bId, d)
                | bId == goalID -> d
                | otherwise -> iter (insertPaths que visited (nextPaths path)) where
                    insertPaths q v [] = (q, v)
                    insertPaths q v (p@(_,x,_):ps) = insertPaths (p Seq.<| q) (M.insert x () visited) ps
                    nextPaths path@(b, bId, d) = [(x, xId, d+1)| (x, xId) <- nextBoards, notVisited xId] where        
                        notVisited x = M.notMember x visited
                        boards = [swapAt (b !! q) b | q <- dest!p]
                        nextBoards = [(x, generateID x)| x <- boards]
                        p = fromJust $ elemIndex 0 b
    goalID= 123456780
    start = concat lst
    dest  = listArray (0, maxAdr) [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]] 
    generateID board = foldl' (\b a-> 10*b+a) 0 board

swapAt v = iter where
    iter [] = []
    iter (x:xs)
        | x == 0 = v:iter xs
        | x == v = 0:iter xs
        | otherwise = x:iter xs

readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

readIntList:: IO [Int]
readIntList = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main :: IO() 
main = do
    l <- replicateM size readIntList
    print $ solver l



Measured memory_bytes: 68532
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
int main(){
    string s;
    int k;
    while (scanf("%d",&k)!=EOF) {
        cin>>s;
        if (s.size()<=k)
            cout <<s << endl;
        else
            cout << s.substr(0,k) << "..." << endl;
    }
    return 0;
}



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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

string s;

int main() {
	cin >> s;
	
	inc(i, 3) {
		     if(s[i] == '1') { s[i] = '9'; }
		else if(s[i] == '9') { s[i] = '1'; }
	}
	
	cout << s << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main() {
  string s;
  int cnt = 0;

  while (cin >> s) {
    bool flag = true;
    for (int i = 0; i < s.length(); ++i)
      if (s[i] != s[s.length()-i-1])
        flag = false;

    cnt += int(flag);
  }

  cout << cnt << endl;
}


Measured memory_bytes: 3120
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <float.h>
#include <math.h>

int search(long long s[], int len, long long target)
{
    int upper, lower, middle;
    upper = len + 1;
    lower = 0;

    while (1) {
        middle = (upper + lower) / 2;
        if (s[middle] < target && target < s[middle + 1]) {break;}
        if (s[middle] < target) {lower = middle;} else {upper = middle;}
    }
    //    printf("%d %d %d, %lld %lld %lld\n", upper, lower, middle, s[middle], target, s[middle + 1]);

    return middle;
}

long long solve(int a, int b, long long s[], long long t[], long long x)
{
    int s_ptr, t_ptr;
    long long s_minus, s_plus;
    long long t_minus, t_plus;
    long long ans;
    long long distance;

    ans = LLONG_MAX;

    //search
    //for (s_ptr = 0; s[s_ptr] < x; s_ptr++) {/* NOP */}
    //for (t_ptr = 0; t[t_ptr] < x; t_ptr++) {/* NOP */}
    s_ptr = search(s, a, x) + 1;
    t_ptr = search(t, b, x) + 1;
    s_minus = s[s_ptr - 1];
    t_minus = t[t_ptr - 1];
    s_plus = s[s_ptr];
    t_plus = t[t_ptr];

    // 左に二回
    distance = (s_minus < t_minus)?(x - s_minus):(x - t_minus);
    ans = (ans < distance)?(ans):(distance);

    // 右に二回
    distance = (s_plus < t_plus)?(t_plus - x):(s_plus - x);
    ans = (ans < distance)?(ans):(distance);

    // 左に行って，右に行く
    if (s_minus < t_minus) {
        distance = (x - t_minus) + (s_plus - t_minus);
    } else {
        distance = (x - s_minus) + (t_plus - s_minus);
    }
    ans = (ans < distance)?(ans):(distance);

    // みぎ，ひだり
    if (s_plus < t_plus) {
        distance = (s_plus - x) + (s_plus - t_minus);
    } else {
        distance = (t_plus - x) + (t_plus - s_minus);
    }
    ans = (ans < distance)?(ans):(distance);

    return ans;
}

int main(int argc, char *argv[])
{
    int a, b, q;
    long long s[100002], t[100002], x[100000];
    int i;
    int ans;

    scanf("%d %d %d", &a, &b, &q);

    for (i = 1; i <= a; i++) { //shrine
        scanf("%lld", &s[i]);
    }
    s[0] = LLONG_MIN / 4;
    s[i] = LLONG_MAX / 4;
    
    for (i = 1; i <= b; i++) { //temple
        scanf("%lld", &t[i]);
    }
    t[0] = LLONG_MIN / 4;
    t[i] = LLONG_MAX / 4;

    for (i = 0; i < q; i++) { //start pos
        scanf("%lld", &x[i]);
    }

    for (i = 0; i < q; i++) {
        printf("%lld\n", solve(a, b, s, t, x[i]));
    }

    return 0;
}


Measured memory_bytes: 3584