akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	int n, k, s;
 	cin >> n >> k >> s;
 	if (s == (int) 1e9)
 	{
 		for (int i = 1; i <= k; i++) cout << s << ' ';
 		for (int i = k + 1; i <= n; i++) cout << "1 ";
 	}
 	else
 	{
 	 	for (int i = 1; i <= k; i++) cout << s << ' ';
 	 	for (int i = k + 1; i <= n; i++) cout << s + 1 << ' ';
 	}
 	return 0;
}

Measured memory_bytes: 1280
//LETS START AGAIN
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define F first 
#define S second
#define int long long int 
signed main() 
{ 
    fast;
    map<int,vector<int>> mp;
    int n;
    cin>>n;
    int a[n+1];
    int pre[n+2]={};
    mp[0].pb(0);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pre[i] = pre[i-1]+a[i];
        mp[pre[i]].pb(i);
    }
    int ans = 0;
    for(auto x:mp)
    {
        vector<int> v = x.second;
        int nn = v.size();
        //cout<<x.first<<" "<<nn<<endl;
        for(int i=0;i<nn;i++)
            ans+=(i);
    }
    cout<<ans;
} 



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

int main() {
    bool exist0 = false;
    int n;
    long long int ans = 1;
    vector<long long int> a;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        long long int data;
        cin >> data;
        if(data == 0) exist0 = true;
        a.push_back(data);
    }
    if(exist0)
    {
        cout << 0 << endl;
        return 0;
    }
    for(int i=0; i<n; i++)
    {
        if(a[i] < LONG_LONG_MAX / ans)
        {
            ans *= a[i];
            if(ans > 1000000000000000000)
            {
                cout << -1 << endl;
                return 0;
            }
        }
        else
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 4320
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    ans=0
    while n:
        n//=k
        ans+=1
    print(ans)

main()

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

int main(){
    string S; cin >> S;
    bool A = false;
    bool B = false;
    bool C = false;
    if(S[0] == 'A') A = true;
    int cnt = 0;
    for(int i = 2; i < S.size()-1; i++){
        if(S[i] == 'C' ) {
            cnt++;
        }
    }
    
    if(cnt == 1) B = true;
    int flag = 0;
    for(int i = 0; i < S.size(); i++){
        if(islower(S[i])) flag++;
    }
    if(flag == S.size()-2) C = true;
    
    if(A == true && B == true && C == true) cout << "AC";
    else cout << "WA";
    
}

Measured memory_bytes: 256
def resolve():
    N, M, C = map(int, input().split())
    B = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        count = 0
        for j in range(M):
            count += A[i][j]*B[j]
        if count+C>0:
            ans += 1
    print(ans)
resolve()

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

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

    double res = (double)0.0;

    for (int i=1; i<=n; i++) {
        double ret = (double)1.0;

        for (int num=i; num<k; num<<=1) {
            ret *= (double)0.5;
        }

        res += ret;
    }

    printf("%.10lf\n", res / (double)n);

    return 0;
}


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

public class Main {

    //https://atcoder.jp/contests/dp/tasks/dp_c
    public static void main( String[] args ) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = scanner.nextInt();
            arr[i][1] = scanner.nextInt();
            arr[i][2] = scanner.nextInt();
        }

        int[][] dp = new int[n][3];

        for (int[] ay : dp)
            Arrays.fill(ay, -1);

        solveBottomUp(arr, dp);
    }
  
  private static void solveBottomUp( int[][] arr, int[][] dp ) {
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][2];

        for (int i = 1; i < arr.length; i++) {

            //At each day Taro can do 3 activities...
            for (int j = 0; j < 3; j++) {

                //Next day activity should be different from Cur-selected Activity
                if (j == 0) {
                    dp[i][0] = Math.max(dp[i - 1][1] + arr[i][0], dp[i - 1][2] + arr[i][0]);
                } else if (j == 1) {
                    dp[i][1] = Math.max(dp[i - 1][2] + arr[i][1], dp[i - 1][0] + arr[i][1]);
                } else {
                    dp[i][2] = Math.max(dp[i - 1][1] + arr[i][2], dp[i - 1][0] + arr[i][2]);
                }
            }
        }

        System.out.println(Math.max(dp[arr.length - 1][2], Math.max(dp[arr.length - 1][0], dp[arr.length - 1][1])));
    }
}

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

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<vector<int>> a(n, vector<int>(m));
  vector<int> c(n);
  rep(i, n) {
    cin >> c[i];
    rep(j, m) {
      cin >> a[i][j];
    }
  }
  int ans = 10000000;
  rep(i, 1<<n) {
    int cost = 0;
    vector<int> level(m);
    rep(j, n) {
      if((i>>j)&1) {
        cost += c[j];
        rep(k, m) {
          level[k] += a[j][k];
        }
      }
    }
    bool flag = true;
    rep(k, m) {
      if(level[k] < x) flag = false;
    }
    if(flag) {
      ans = min(ans, cost);
    }
  }
  if(ans == 10000000) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}
        

Measured memory_bytes: 3580
k,n = map(int,input().split())

a = list(map(int,input().split()))
ans = 0
gr = 0
for i in range(1,n):
    if(a[i] - a[i-1] > gr):
        gr = a[i] - a[i-1]

if((k - a[n-1]) + a[0] > gr):
    gr = (k - a[n-1]) + a[0]
# print(gr)

print(k - gr)


Measured memory_bytes: 77644
###
### atcorder test program
###

import sys

### math class
class math:
    ### pi
    pi = 3.14159265358979323846264338

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Prime number search
    def Pnum(self, a):
        if a == 1: return False
        for i in range(2,int(a**0.5)+1):
            if a % i == 0:
                return False
        return True

    ### Circle area
    def caria(self, r):
        return r*r*self.pi

math = math()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

#A, B, C = [int(x) for x in input().split()]

N = int(input())
S = []
AB = [chr(i) for i in range(ord('a'), ord('z')+1)]

for i in range(N):
    S.append(input())

for i in AB:
    countmin = 114514
    for j in S:
        if countmin > j.count(i):
            countmin = j.count(i)
        #print(i,countmin,j.count(i))

    for j in range(countmin):
        print(i,end="")
    
print("")


Measured memory_bytes: 3064
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=1e18;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,cnt=0;
  cin >> n;
  cnt+=n/500*1000;
  cnt+=(n%500)/5*5;
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	string a;
  	string b;
  	cin >> a;
  	cin >> b;
  	int n = a.size();
  	int m = b.size();
  	int count = 0;
  	int min = INT_MAX;
  	for(int i=0;i+m-1<n;i++)
    {
      	count = 0;
    	for(int j=0;j<m;j++)
        {
        	if(a[i+j]!=b[j])
            {
            	count++;
            }
        }
      	if(min>count)
        {
          min = count;
        }
    }
  	cout << min << endl;
}


Measured memory_bytes: 3600
<?php
$n = trim(fgets(STDIN));
$v = explode(' ', trim(fgets(STDIN)));

rsort($v);

for ($i = 0; $i < $n - 1; $i++) {
    $min1 = array_pop($v);
    $min2 = array_pop($v);
    $ave = ($min1 + $min2) / 2;
    array_push($v, $ave);
    rsort($v);
}

echo $v[0] . PHP_EOL;


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

int check(long long int *a, int n);
void div(long long int *a, int n);

int main(){
    int i,n,res = 0;
    long long int a[200] = {0};

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

    while( 1 ){
        if( check( a, n) ){
            break;
        }
        else{
            div( a, n );
            res++;
        }
    }

    cout << res << "\n";
}

int check(long long int *a, int n){
    int i,res = 0;

    for( i = 0; i < n; i++){
        if( a[i] % 2 == 1 ){
            res++;
            break;
        }
    }

    return res;
}

void div(long long int *a, int n){
    int i;
    for( i = 0; i < n; i++ ){
        a[i] /= 2;
    }
}


Measured memory_bytes: 256
W,H,N=map(int,input().split())
m=[[0]*W for i in range(H)]
ans=W*H

def c(a,b):
    global ans
    if m[a][b]==0:
        m[a][b]=1
        ans-=1
for i in range(N):
    x,y,a=map(int,input().split())
    if a==1:
        for j in range(H):
            for k in range(x): c(j,k)
    if a==2:
        for j in range(H):
            for k in range(x,W): c(j,k)
    if a==3:
        for j in range(y):
            for k in range(W): c(j,k)
    if a==4:
        for j in range(y,H):
            for k in range(W):c(j,k)
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*

*/

ll n,fact[100]={},ans=0,a=0,b=0,c=0,d=0,e=0,f=0;
vector<ll> pl;

//nまでの素数表を返す
vector<ll> prime(ll n){
	ll visited[300010]={};
	vector<ll> p;
	reg(i,2,n){
		if(visited[i]==0){
			p.push_back(i);
			reg(j,2,n){
				if(j*i>n)break;
				visited[i*j]=1;
			}
		}
	}
	return p;
}

int main(void){
	cin>>n;
	pl = prime(n);
	reg(i,1,n){
		ll m=i;
		rep(j,pl.size()){
			if(m==1)break;
			while(m%pl[j]==0){
				fact[j]++;
				m/=pl[j];
			}
		}
	}
	// rep(i,pl.size())cout<<fact[i]<<endl;
	//74
	rep(i,pl.size())if(fact[i]>=74)ans++;
	//2,24
	rep(i,pl.size()){
		if(fact[i]>=24){
			a++;
		}else if(fact[i]>=2){
			b++;
		}
	}
	ans+=a*b + a*(a-1)/2*2;
	//4,14
	rep(i,pl.size()){
		if(fact[i]>=14){
			c++;
		}else if(fact[i]>=4){
			d++;
		}
	}
	ans+=c*d + c*(c-1)/2*2;
	//2,4,4
	rep(i,pl.size()){
		if(fact[i]>=4){
			e++;
		}else if(fact[i]>=2){
			f++;
		}
	}
	ans+=f*e*(e-1)/2 + e*(e-1)*(e-2)/6*3;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
def solve():
    N, M = map(int, input().split())
    l = []
    for i in range(1, N+1):
        a = i
        c = 0
        while a < M:
            a *= 2 
            c += 1
        b = 1 if c == 0 else (0.5)**c
        l.append(b * (1/N))
    return sum(l)

print(solve())

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

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

using namespace std;

typedef long long LL;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "[ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "]";

    return os;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    stack<int> S1;
    stack<pair<int, int>> S2;

    string s;
    cin >> s;

    int sum = 0;

    REP(i, s.size()) {
        if (s[i] == '\\') {
            S1.push(i);
        }

        if (s[i] == '/') {
            if (S1.empty()){
                continue;
            }
            int j = S1.top();
            S1.pop();

            int current = i - j;
            sum += current;

            if (S2.empty()) {
                S2.push(make_pair(j, current));
                continue;
            }

            while (!S2.empty()) {
                auto p = S2.top();
                if (p.first <= j) {
                    break;
                }
                S2.pop();
                current += p.second;
            }

            S2.push(make_pair(j, current));
        }
    }

    cout << sum << endl;

    int size = S2.size();
    cout << size;

    stack<int> ans;
    REP(i, size) {
        ans.push(S2.top().second);
        S2.pop();
    }

    REP(i, size) {
        cout << " " << ans.top();
        ans.pop();
    }

    cout << endl;
}



Measured memory_bytes: 3252
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <cmath> 
using namespace std;


int main(){ 
    long long int x;
    int ansi,ansj;
    long long int pm[130];
    cin >>x;
    rep(i,130){
        pm[i] = i*i*i*i*i;
    }

    rep(i,122){
        for(int j = 0; j<=i; j++){
            if(pm[i]-pm[j]==x){
                ansi = i;
                ansj = j;
            }
        }
    }
    rep(i,100){
        for(int j = 0; j<=i; j++){
            if(pm[i]+pm[j]==x){
                ansi = i;
                ansj = -j;
            }
        }
    }
    cout << ansi<< " " << ansj <<endl;
}

Measured memory_bytes: 3164
#include <iostream>
#include <vector>
#include <string>

inline void chmin(int &x, int y) {
    if(x > y) x = y;
}

int main() {
    std::string s, t; std::cin >> s >> t;
    int n = s.size(), m = t.size();
    std::vector<std::vector<int>> dp(n+1, std::vector<int>(m+1, n+m));
    dp[0][0] = 0;
    for(int i = 0; i<n+1;++i) {
        for(int j = 0; j < m+1; ++j) {
            if(i > 0) chmin(dp[i][j], dp[i-1][j] + 1);
            if(j > 0) chmin(dp[i][j], dp[i][j-1] + 1);
            if(i > 0 && j > 0) chmin(dp[i][j], dp[i-1][j-1] + ((s[i-1] == t[j-1])?0:1));
        }
    }
    std::cout << dp[n][m] << std::endl;
}


Measured memory_bytes: 6828
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int h, w;
  cin >> h >> w;
  char m[h][w];
  for (int i=0; i<h; ++i) {
    for (int j=0; j<w; ++j) cin >> m[i][j];
  }
  vector< int > dx = {-1, -1, -1, 0, 0, 1, 1, 1};
  vector< int > dy = {-1, 0, 1, -1, 1, -1, 0, 1};
  for (int i=0; i<h; ++i) {
    for (int j=0; j<w; ++j) {
      if (m[i][j]=='#') continue;
      int ans = 0;
      for (int k=0; k<8; ++k) {
        if (0<=i+dx[k] && i+dx[k]<h && 0<=j+dy[k] && j+dy[k]<w && m[i+dx[k]][j+dy[k]]=='#') ans++;
      }
      m[i][j] = (char)(ans+'0');
    }
  }
  for (int i=0; i<h; ++i) {
    for (int j=0; j<w; ++j) {
      cout << m[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
      a+=b;
      b=1;
	for(int i=1;i<8;i++){
		b*=10;
		if(a<b){
			cout<<i<<endl;
			break;
		  }
		}
	}
	return 0;
	}


Measured memory_bytes: 3100
n = int(input())
xyh = [tuple(map(int, input().split())) for _ in range(n)]

for i in range(n):
    if xyh[i][2] > 0:
        ca = i

for x in range(0, 101):
    for y in range(0, 101):
        flag = True
        H = xyh[ca][2] + abs(xyh[ca][0] - x) + abs(xyh[ca][1] - y)
        for xx, yy, hh in xyh:
            h = max(H - abs(xx - x) - abs(yy - y), 0)
            if hh != h:
                flag = False
                break
        if flag:
            print(x, y, H)
            exit()


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
	int T;
	while(~scanf("%d",&T))
	{
		int sum = 0;
		for(int i=0;i<T;++i)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			sum+=(b-a+1);
		}
		printf("%d\n",sum);
	}
}

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;
using pii = pair<int, int>;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    //
    string s, t; cin >> s >> t;

    int min_cnt = 1000;
    rep(i, s.length() - t.length() + 1) {
        int cnt = 0;
        rep(j, t.length()) {
            if (s[i+j] != t[j]) cnt++;
        }
        if (min_cnt > cnt) min_cnt = cnt;
    }

    cout << min_cnt << endl;
    //

    return 0;
}


Measured memory_bytes: 3596
N = int(input())
S = input()
Sr = []

al = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

for i in range(len(S)):
  m = al.index(S[i])
  n = (1 + m + N) % 26 - 1
  Sr.append(al[n])
  
print(''.join(Sr))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  int N, M; cin >> N >> M;
  vector<int> k(M);
  vector<vector<int>> s(M, vector<int>());
  REP(i, M) {
    cin >> k[i];

    REP(j, k[i]) {
      int ss; cin >> ss;
      s[i].push_back(ss);
    }
  }

  vector<int> p(M); REP(i, M) cin >> p[i];

  int ans = 0;
  for (int i = 0; i < (1<<N); ++i) {

    bool ok = true;
    for (int j = 0; j < M; ++j) {

      int sum = 0;
      for (int kk = 0; kk < k[j]; ++kk) {
        sum += i>>(s[j][kk]-1)&1;
        // cout << "Debug: " << (i>>(s[j][kk]-1)&1) << endl;
      }

      if (sum % 2 != p[j]) {
        ok = false;
        break;
      }
      // for (int j = 0; j < N; ++j) {
      //   cout << (i>>j&1);
      // }
    }

    if (ok) {
      ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void)
{
	int n=0,s[1000],i,j;
	double a,a2,m=0,M=0,N=0;

	
	

	for(j=1;j>0;j++)
	{
	
		scanf("%d",&n);
		

		if(n==0)
		{
			j = j*(-1);
		}
	
		else
		{
			

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

			m = m/n;

			for(i=0;i<n;i++)
			{

				M = pow(s[i]-m,2);
				
				N = M + N;
			}

			a2 = N/n;

			a= sqrt(a2);

			printf("%f\n",a);

			m =0;
			M =0;
			N =0;

		}

	}

	
	return 0;


}

Measured memory_bytes: 636
N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = []
if a[0] > 0:
    x = a[0]
    for i in range(1, N - 1):
        ans.append((x, a[i]))
        x -= a[i]
    ans.append((a[-1], x))
    x = a[-1] - x
elif a[-1] < 0:
    x = a[-1]
    for i in range(N - 2, -1, -1):
        ans.append((x, a[i]))
        x -= a[i]
else:
    x = a[0]
    for i in range(1, N - 1):
        if a[i] >= 0:
            ans.append((x, a[i]))
            x -= a[i]
    ans.append((a[-1], x))
    x = a[-1] - x
    for i in range(1, N - 1):
        if a[i] < 0:
            ans.append((x, a[i]))
            x -= a[i]

print(x)
for a, b in ans:
    print(a, b)

Measured memory_bytes: 63500
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let s: u64 = sc.read();
    let x = (s as f64).sqrt() as u64;
    if s - x * x == 0 {
        print!("0 0 {} {} {} {}", x, 0, 0, x);
        return 
    } 
    let y = x + 1;
    let t = y * y - s;
    
    print!("0 0 {} {} {} {}", y, 1, t, y);
    
    
    
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}
pub mod utils {
    const DYX: [(isize, isize); 8] = [
        (0, 1),   //right
        (1, 0),   //down
        (0, -1),  //left
        (-1, 0),  //top
        (1, 1),   //down right
        (-1, 1),  //top right
        (1, -1),  //down left
        (-1, -1), //top left
    ];

    pub fn try_adj(y: usize, x: usize, dir: usize, h: usize, w: usize) -> Option<(usize, usize)> {
        let ny = y as isize + DYX[dir].0;
        let nx = x as isize + DYX[dir].1;
        if ny >= 0 && nx >= 0 {
            let ny = ny as usize;
            let nx = nx as usize;
            if ny < h && nx < w {
                Some((ny, nx))
            } else {
                None
            }
        } else {
            None
        }
    }
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8444
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <bitset>
#include <complex>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef complex<double> CD;

int main() {
	while (true) {
		int n; cin >> n;
		if (n == -1)break;

		int mo = 1150 + min(10, max(0, n - 10)) * 125 + min(10, max(0, n - 20)) * 140 + max(0, n - 30) * 160;
		Cout(4280 - mo);
	}
}


Measured memory_bytes: 3108
n, m, x, y = map(int, input().split())
l_a = list(map(int, input().split()))
l_b = list(map(int, input().split()))
l_a.append(x)
l_b.append(y)
l_a = sorted(l_a)
l_b = sorted(l_b)
if l_a[-1] < l_b[0]:
    print("No War")
else:
    print("War")

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INT_INF 1000000000
#define DOUBLE_INF 1e18
#define MOD 1000000007
#define mod(x) ((x % MOD) + MOD) % MOD

using namespace std;

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

struct edge
{
  int to;
  ll cost;
};

const int MAX_NODE = 100002;
const ll INF_DIST = 1e18;

void dijkstra(int s, vector<edge> *G, ll *d)
{
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d, d + MAX_NODE, INF_DIST);
  d[s] = 0;
  que.push(P(0, s));
  while(!que.empty()) {
    ll temp_cost = que.top().first;
    int from = que.top().second;
    que.pop();
    if (d[from] < temp_cost) continue;
    for (int i = 0; i < G[from].size(); i++) {
      edge e = G[from][i];
      if (d[e.to] > d[from] + e.cost) {
        d[e.to] = d[from] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

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

  ll d[2][MAX_NODE];
  vector<edge> G[2][MAX_NODE];

  ll u, v, a, b;
  for (int i = 0; i < m; i++) {
    cin >> u >> v >> a >> b;
    G[0][u].push_back((edge){ v, a });
    G[0][v].push_back((edge){ u, a });
    G[1][u].push_back((edge){ v, b });
    G[1][v].push_back((edge){ u, b });
  }

  dijkstra(s, G[0], d[0]);
  dijkstra(t, G[1], d[1]);

  ll cost[MAX_NODE];
  cost[n-1] = d[0][n] + d[1][n];

  for (int i = n-2; i >= 0; i--) {
    cost[i] = min(cost[i+1], d[0][i+1] + d[1][i+1]);
  }

  for (int i = 0; i < n; i++) {
    cout << (ll)pow(10, 15) - cost[i] << endl;
  }

  return 0;
}


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

int main() {
  int n,m;
  cin>>n>>m;
  
  int a[n];
  int s=0;
  for(int i=0; i<n; i++){
    cin >> a[i];
    s += a[i];
  }
  
  int x=4*m;
  int y;
  if(s % x == 0) y=s/x;
  else y=s/x+1;
  
  int count=0;
  
  for(int i=0; i<n; i++){
    if(a[i] >= y) count++;
  }
  
  if(count >= m) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e9;
typedef pair<int, int> pi;
ll a[100001], b[100001];
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += a[i];
        b[a[i]]++;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        ll fq, sq;
        cin >> fq >> sq;
        ans -= fq * b[fq];
        ans += sq * b[fq];
        b[sq] += b[fq];
        b[fq] = 0;
        cout << ans << "\n";
    }
}

Measured memory_bytes: 5168
n, c, k = gets.split.map(&:to_i)
ts = []
n.times do
  ts << gets.to_i
end
ts.sort!

ans = 0
cur = 0
while cur < n
  current_time = ts[cur]
  a = ts.bsearch_index { |t| t > current_time + k } || 10 ** 20
  cur = [cur+c, a].min
  ans += 1
end
puts ans

Measured memory_bytes: 4016
//GCD FREQUENCY COUNTER WITH INC-EXC BY ADANCITO

//WHAT DOES THIS ALGORITHM DO?
/*
 
 imagine that for every ordered pair (i, j), 0 <= i, j <= maxN, we did
 res[gcd(i, j)] += one[i] * two[j]
 
 this algorithm calculates the final value of res in O(nlgn)
 
 remember to call precalculations() at the beginning of the program
 
 */

#include <iostream>
#include <string.h>
#include <ctime>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>
#include <vector>
#define se second
#define fi first

using namespace std;
const int maxN = 1e5 + 8, MOD = 1e9 + 7;

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

int n, arr[maxN], sorted[maxN];

int T[maxN << 2];

int cnd;
void update(int w, int x){
    w += cnd;
    while(w){
        T[w] += x;
        w >>= 1;
    }
}

int query(int l, int r){
    int ret = 0;
    for(l += cnd, r += cnd; l < r; l >>= 1, r >>= 1){
        if(l & 1) ret += T[l++];
        if(r & 1) ret += T[--r];
    }
    return ret;
}

ll eval(ll m){
    memset(T, 0, sizeof T);
    cnd = n * 3 + 6;
    ll ans = 0;
    for(int i = n - 1; i >= 0; i--){
        int vl = 1;
        if(arr[i] < m) vl = -1;
        update(0, 1);
        cnd -= vl;
        
        
        ans += query(-n, 0);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i]; sorted[i] = arr[i];
    }
    
    sort(sorted, sorted + n);
    
    ll lim = ll(n) * ll(n + 1) >> 2, l = 0, m, r = n;
    
    //cout << lim << '\n';
    
    while(l + 1 < r){
        m = (l + r) >> 1;
        if(eval(sorted[m]) <= lim){//a huevo!, tirale a mas
            l = m;
        }
        else{//te mamaste, bajale de huevos
            r = m;
        }
    }
    
    cout << sorted[l] << '\n';
    
}

//99999000001
//00000999999


Measured memory_bytes: 2560
from collections import Counter
import itertools
ans=0
n=int(input())
ls=["M","A","R","C","H"]
S=Counter([i for i in list(map(lambda x:x[0] ,[input() for i in range(n)])) if i in ls])

for i in itertools.combinations(S.values(),3):
  ans+=i[0]*i[1]*i[2]
print(ans)


Measured memory_bytes: 10872
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
typedef pair<int, int> PAIR;
int main(){
int N; cin >> N; string S[N]; vector<PAIR> U, V;
REP(i, N){ 
  cin >> S[i];
  int l=0, m=0, n=S[i].size();
  REP(j, n){ l=(S[i][j]=='(')?l+1:l-1; m=min(m, l); }
  if(l>=0){ U.push_back(make_pair(-m, l)); }
  else{ V.push_back(make_pair(-(m-l), -l)); }
}
sort(U.begin(), U.end()); sort(V.begin(), V.end());
int l=0, m=0, u=U.size(), v=V.size();
REP(i, u){ if(l-U[i].first>=0){ l=l+U[i].second; }else{ cout << "No\n"; return 0; } }
REP(i, v){ if(m-V[i].first>=0){ m=m+V[i].second; }else{ cout << "No\n"; return 0; } }
if(l==m){ cout << "Yes\n"; }else{ cout << "No\n"; }
}

Measured memory_bytes: 42400
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
	static final int MOD = 1000000007;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		//入力
		long n = sc.nextLong();
		sc.close();

		//処理
		int ans = 10;
		for(long i = 1; i * i <= n; i++){
			if(n % i == 0){
				long j = n / i;
				long greater = Math.max(i,j);
				int temp = 0;
				while(greater != 0){
					temp++;
					greater /= 10;
				}
				ans = Math.min(ans, temp);
			}
		}

		//出力	
		out.println(ans);
		out.flush();
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const long long M = 1e8 ;
int main()
{
    ll n,m,k,sum,con,i,x,mx=0;
    cin>>n>>m>>k;
    vector< ll > apre(n+1);
    vector< ll > bpre(m+1);
    for(i=1;i<=n;i++){
        cin>>x;
        apre[i]= apre[i-1]+x;
    }
     for(i=1;i<=m;i++){
        cin>>x;
        bpre[i]= bpre[i-1]+x;
     }
    for(i=0;i<=n;i++){
        sum = k - apre[i];
        if(sum>=0){
            auto it=lower_bound(bpre.begin(),bpre.end(),sum);
            if(*it>sum) it--;
            ll d=it- bpre.begin();
            if(d== (m+1)) d--;
            con = d+i;
            mx = max(con,mx);
        }
        else
            break;
    }
    cout<<mx<<endl;

    return 0;
}



Measured memory_bytes: 6408
#include <bits/stdc++.h> 
 
#define INF (1<<31) - 1 //INT_MAX/2
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;

int main(int argc, char *argv[])
{
    int A, B, C;
    std::cin >> A >> B >> C;

    if (A + B >= C) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No"  << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,K,ans=1;
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		if(ans*2<ans+K)ans=ans*2;
		else ans=ans+K;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int N, i, tmp;
    int A[100002],B[100002];
    
    scanf("%d",&N);
    
    for(i=1; i<=N; i++){
        scanf("%d",&A[i]);
    }
    
    for(i=1; i<=N; i++){
        tmp = A[i];
        B[tmp] = i;
    }
    
    for(i=1; i<=N; i++){
        printf("%d ",B[i]);
    }
        
    printf("\n");
        
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};

int main() {
    int H,W; cin >> H >> W;
    char A[60][60];
    REP(i,H){
        REP(j,W){
         cin >> A[i][j];
        }
    }
    REP(i,H){
        REP(j,W){
            if(A[i][j]=='#')continue;
            int c = 0;
            REP(k,8){
                if(i+dy[k] >= 0 && i+dy[k] < H
                && j+dx[k] >= 0 && j+dx[k] < W
                && A[i+dy[k]][j+dx[k]]=='#')
                c++;
            }
            A[i][j]='0'+c;
        }
    }
    REP(i,H){
        REP(j,W){
            cout << A[i][j] << flush;
        }
        cout << endl;
    }



    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n,i,p;
    scanf("%d\n",&n);
    int A[n];
    for(i=0;i<n;i++){
        scanf("%d",&p);
        A[p-1]=i+1;
    }
    for(i=0;i<n;i++){
        printf("%d ",A[i]);
    }
    return 0;
}

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

using namespace std;

int A[100000];
int B[100000];
int H, N;
vector<long long int> dp(50000000,5e15);


long long int dpf(int h){
  if(dp[h]<1e15){
    return dp[h];
  }else if(h==0){
    dp[h]=0;
    return 0;
  }else{
    dp[h]=1e14;
    for(int i=0;i<N;i++){
      if(h-A[i]>=0){
        dp[h]=min(dpf(h-A[i])+B[i], dp[h]);
      }
    }
    return dp[h];
  }
}


int main(void){
  cin >> H >> N;
  int maxval=0;
  for(int i=0;i<N;i++){
    int tmp1, tmp2;cin >> tmp1 >> tmp2;
    A[i]=tmp1;
    B[i]=tmp2;
    maxval = max(maxval, tmp1);
  }
  long long int minval=5e15;
  for(int i=maxval-1;i>=0;i--){
    long long int tmp=dpf(H+i);
    if(minval>tmp)minval=tmp;
  }
  cout << minval;
  return 0;
}




Measured memory_bytes: 391552
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0] * N

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

def main():

    for _ in range(N-1):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p-1] += x
    # print(ans)

    dfs(0, -1)
    print(*ans)

if __name__ == "__main__":
    main()


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

int main(){
int A,B,C,D;
  cin>>A>>B>>C>>D;
  if(A+B>C+D){  cout<<"Left"<<endl;  }
  else if(A+B<C+D){  cout<<"Right"<<endl;  }
  else{cout<<"Balanced"<<endl; }
}

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

const string YES = "YES";
const string NO = "NO";

void solve(std::vector<long long> N){
    sort(N.begin(), N.end());
    if(N[0] == 1 && N[1] == 4 && N[2] == 7 && N[3] == 9){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    std::vector<long long> N(4);
    for(int i = 0 ; i < 4 ; i++){
        scanf("%lld",&N[i]);
    }
    solve(std::move(N));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin >> s;
  if(s == "Sunny") cout << "Cloudy" << endl;
  if(s == "Cloudy") cout << "Rainy" << endl;
  if(s == "Rainy") cout << "Sunny" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<cmath>

using namespace std;

typedef long long ll;

int main(){
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> A(x), B(y), C(z);
    for(int i = 0; i < x; i++) cin >> A[i];
    for(int i = 0; i < x; i++) cin >> B[i];
    for(int i = 0; i < x; i++) cin >> C[i];

    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
    sort(C.begin(), C.end(), greater<ll>());
        
    vector<ll> ABC;
    for(int a = 0; a < x; a++)
    {
        for(int b = 0; b < y; b++)
        {
            if((a + 1) * (b + 1) > k) break;
            for(int c = 0; c < z; c++)
            {
                if((a + 1) * (b + 1) * (c + 1) > k) break;

                ABC.push_back(A[a] + B[b] + C[c]);
            }   
        }
    }
    
    sort(ABC.begin(), ABC.end(), greater<ll> ());

    for(int i = 0; i < k; i++)
    {
        cout << ABC[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 1404
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
from collections import deque

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        c = -(-dam//A)
        count += c
        aldam += c*A
        q.append((now+2*D,c*A))

    print(count)

if __name__ == "__main__":
    main()

Measured memory_bytes: 76764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

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

	
	int N, K;
	cin >> N >> K;
	int D[11] = {};
	rep(i, K) {
		int d;
		cin >> d;
		D[d] = 1;
	}

	int kotae;
	for (int i = N; i < 1000000; i++) {
		int kari = i;
		int keta[7] = {};
		int ima = 0;
		while (kari) {
			keta[ima] = kari % 10;
			kari /= 10;
			ima++;
		}
		int OK = 1;
		rep(ii, ima) {
			if (D[keta[ii]] == 1) OK = 0;
		}
		if (OK) {
			kotae = i;
			break;
		}
	}

	co(kotae);

	Would you please return 0;
}

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

int X,Y,S;

int tax(double rate,int price){
    return price*(100+rate)/100;
}

int solve(){
    int maximum = 0;
    for(int i=1; i<S; ++i){
        for(int j=1; j<S; ++j){
            if(tax(X,i)+tax(X,j) == S)
                maximum = max(maximum, tax(Y,i)+tax(Y,j));
        }
    }
    return maximum;
}

int main(){
    while(cin >> X >> Y >> S && X>0){
        cout << solve() << endl;
    }
}

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

int main(){
  int n;
  int count=0,ans=0;
  cin >> n;
  int check = n;
  while(check){
    check = check/10;
    count++;
  }

  for(int i=count;i>0;i--){
    if(i%2&&i==count){
      ans += n-(int)(pow(10, count-1)-1);
    }else if(i%2){
      ans += int(pow(10,i)-pow(10,i-1));
    }
  }
  cout << ans << endl; 
  
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll a,b,n;
  cin>>a>>b>>n;
  ll k=min(b-1,n);
  COUT(a*k/b-k/b*a);
}

Measured memory_bytes: 3588
N, M = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
x.sort()

steps = []
for i in range(M - 1):
    steps.append(x[i + 1] - x[i])
steps.sort()

if N >= M:
    res = 0
elif N == 1:
    res = max(x) - min(x)
else:
    res = sum(steps[:-N + 1])
print(res)

Measured memory_bytes: 13968
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	cout<<min(b/a,c)<<endl;
}


Measured memory_bytes: 256
import           System.IO
import           Control.Monad
import           Control.Applicative
import           Control.Monad.State
import           Data.List

calc :: [Int] -> String
calc (a : b : c : _) | a ^ 2 + b ^ 2 == c ^ 2 = "YES"
                     | otherwise              = "NO"

main = do
  n     <- readLn
  lines <- replicateM n getLine
  mapM (putStrLn . calc . sort . (map read) . words) lines



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

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int h, w, a, b;
    cin>>h>>w>>a>>b;
    // 前処理
    COMinit();
    long long int all = COM(h+w-2, h-1);

    for (int i=0; i<a; i++){
      all=all%MOD-(COM(h+b-i-2, h-i-1)%MOD*COM(w-b-1+i, w-b-1))%MOD;
      if (all < 0) all += MOD;
    }

    cout<<all%MOD<<endl;    
}

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		sc.close();
		
		Arrays.sort(arr);
		int pointer = 0;
		int ans = 0;
		int nowVal = arr[0];
		int nowCnt=1;
		while(pointer < arr.length) {
			nowVal = arr[pointer];
			nowCnt = 1;
			while(pointer + 1 < arr.length && arr[pointer+1] == nowVal) {
				nowCnt++;
				pointer++;
			}
			
			if(nowVal < nowCnt) {
				ans += nowCnt - nowVal;
			}else if(nowVal > nowCnt) {
				ans += nowCnt;
			}
			pointer++;
		}
		
		System.out.println(ans);
	}
}


Measured memory_bytes: 50164
#include<stdio.h>
#include<stdlib.h>

int main(){
  
 long long int n,sh,sl,p=1,k=1;
  scanf("%lld",&n);
 long long int a[n];
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  
  sh=a[n-1];
  sl=a[0];
  
  while(p+k<n){
    if(sl<=sh){
      sl+=a[p];
      p++;
    }
    else{
      sh+=a[n-k-1];
      k++;
    }
  }
  
  printf("%lld",abs(sh-sl));
  
  return 0;
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str1 = sc.next();
		String str2 = sc.next();
		sc.close();
		
		if(str1.charAt(0) == str2.charAt(2)
				&& str1.charAt(1) == str2.charAt(1)
				&& str1.charAt(2) == str2.charAt(0)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


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

int main(){
	int a, b;
	cin >> a >> b;
	if(a == 1) a = 14;
	if(b == 1) b = 14;
	if(a < b) cout << "Bob" << endl;
	else if(a > b) cout << "Alice" << endl;
	else cout << "Draw" << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanf("%d\n", &n)
	var ws []int
	for i := 0; i < n; i++ {
		var x int
		fmt.Scanf("%d", &x)
		ws = append(ws, x)
	}

	sum := 0
	for _, w := range ws {
		sum += w
	}
	ans := sum
	s1 := 0
	for _, w := range ws {
		s1 += w
		s2 := sum - s1
		var x int
		if s2 > s1 {
			x = s2 - s1
		} else {
			x = s1 - s2
		}
		if x < ans {
			ans = x
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
const long double pi = 3.1415926535897932384626433832795;
int bp(int pow, int n){
    int d = 1;
    while(n)
    {
        if(n%2==1)d=(d*pow)%mod;
        pow=(pow*pow)%mod;
        n/=2;
    }
    return d;
}
int a['R'+'G'+'B'][N];
void solve(){
    int n;
    string s;
    cin>>n>>s;
    for(int i = 0; i < n; i++){
        a['R'][i]=a['R'][i-1];
        a['G'][i]=a['G'][i-1];
        a['B'][i]=a['B'][i-1];
        a[s[i]][i]++;
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(s[i]!=s[j]){
                int t = 'R'+'G'+'B'-s[i]-s[j];
                int d = j-i;
                sum += a[t][n-1]-a[t][j];
                if(s[d+j]==t&&d+j<n)sum--;
            }
        }
    }
    cout<<sum;
}
signed main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Measured memory_bytes: 3704