akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define PR pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0;

//#define int ll

// the balance of the world

signed main(){
  while(1){
    stack<char> s;
    string str;
    getline(cin, str);
    if(str==".") break;
    
    bool ans=1;
    for(int i=0; i<str.size(); i++){
      if(str[i]=='('||str[i]=='['){
        s.push(str[i]);
      }else if(str[i]==')'||str[i]==']'){
        if(s.empty()) ans=0;
        else if(str[i]==']'&&s.top()=='['){
          s.pop();
        }else if(str[i]==')'&&s.top()=='('){
          s.pop();
        }else{
          ans=0;
        }
      }else if(str[i]=='.'){
        if(ans&&s.empty()) cout<<"yes"<<en
        else cout<<"no"<<en
          break;
      }
    }
  }
  RE
}


Measured memory_bytes: 3168
A,V=map(int,input().split())
B,W=map(int,input().split())
T=int(input())

if A<B:
  A_T=A+V*T
  B_T=B+W*T
  if A_T>=B_T:
    print('YES')
  else:
    print('NO')
else:
  A_T=A-V*T
  B_T=B-W*T
  if A_T<=B_T:
    print('YES')
  else:
    print('NO')

Measured memory_bytes: 9192
N, C = map(int, input().split())
tv = [list(map(int, input().split())) for _ in range(N)]

max_t = max(tv, key=lambda x: x[1])[1]
channels = [[0 for _ in range(max_t)] for _ in range(C)]

for s, t, c in tv:
    channels[c - 1][s - 1:t] = [1] * (t - s + 1)

ans = 0
for T in list(zip(*channels)):
    ans = max(ans, sum(T))
print(ans)


Measured memory_bytes: 80492
#include<iostream>
#include<vector>
#include <unordered_map>  
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <sstream>
#include <cmath>
#include <float.h>
using namespace std;



int main(){
	int n, m, x, a[100], sum_a = 0, sum_b = 0;
	cin >> n >> m >> x;
	for (int i = 0; i < 100; ++i) {
		a[i] = 0;
	}
	for (int i = 0; i < m; ++i) {
		int tmp;
		cin >> tmp;
		a[tmp] = 1;
	}
	for (int i = x; i < n; ++i) {
		sum_a += a[i];
	}
	for (int i = x; i > 0; --i) {
		sum_b += a[i];
	}
	if (sum_a > sum_b) {
		cout << sum_b << endl;
	}
	else {
		cout << sum_a << endl;
	}
	return 0;
}

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

int main() {
	int n, q;
	string s;
	cin >> n >> q >> s;
	vector<int> count(n, 0);

	for(int i = 1; i<n; i++){
		if(s[i-1] == 'A' && s[i] == 'C'){
			count[i]++;
		}
		count[i]+=count[i-1];
	}

	for(int i = 0, l, r; i<q; i++){
		cin >> l >> r;
		cout << count[r-1]-count[l-1] << '\n';
	}
}

Measured memory_bytes: 1408
#include <iostream>

using namespace std;

int main(void) {
	char c;
	cin >> c;
	if (c == 'S') {
		cout << "Cloudy" << endl;
	}
	else if (c == 'C') {
		cout << "Rainy" << endl;
	}
	else {
		cout << "Sunny" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
from collections import Counter, deque

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

MOD = 10 ** 9 + 7

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1
if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
elif n_minus == N and K % 2 == 1:
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        if len(plus) == 0:
            minus.pop()
            for a in A[K:]:
                if a >= 0:
                    plus.append(a)
                    break
        else:
            p = None
            m = None
            for a in A[K:]:
                if a >= 0 and p is None:
                    p = a
                if a < 0 and m is None:
                    m = a
                if p is not None and m is not None:
                    break

            if m is None:
                minus.pop()
                plus.append(p)
            elif p is None:
                plus.pop()
                minus.append(m)
            elif minus[-1] * m > plus[-1] * p:
                plus.pop()
                minus.append(m)
            else:
                minus.pop()
                plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)


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

int main()
{
    long long h,n;
    cin>>h>>n;
    
    long long a[n],i,sum=0;
    
    for(i=0;i<n;i++){
        cin>>a[i];
        sum +=a[i];
    }
    
    if(sum>=h){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    return 0;
}


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

int main(){
    ll N, W;  cin >> N >> W;
    vector<ll> w(N+1), v(N+1);
    for(int i=1; i<=N; i++) cin >> w[i] >> v[i];

    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(N+1, vector<ll>(W+1, 0));
    for(int j=0; j<=W; j++){
        if(j == w[1]) dp[1][j];
    }

    for(int i=1; i<=N; i++){
        for(int j=0; j<=W; j++){
            if(w[i] <= j){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<=W; i++) ans = max(ans, dp[N][i]);
    cout << ans << endl;
}


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

int main() {
	long long N;
	double ANS = 0.0;
	double X[8], Y[8];
	vector<long long> V;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
	for (int i = 0; i < N; i++) V.push_back(i);
	do {
		double COUNT = 0.0;
		for (int i = 0; i < N - 1; i++) {
			long long DX = X[V[i]] - X[V[i + 1]], DY = Y[V[i]] - Y[V[i + 1]];
			COUNT += sqrt(DX * DX + DY * DY);
		}
		ANS += COUNT;
	} while (next_permutation(V.begin(), V.end()));
	for (int i = 1; i <= N; i++) ANS /= (double)i;
	printf("%.12lf\n", ANS);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll INF = ll(1e17)+5;

void solve(long long N, std::vector<long long> A){
    if(N==0){
        if(A[0] >1){
            cout << -1 << endl;
        }else{
            cout << A[0] << endl;
        }
        return;
    }
    ll maxBranchNum[N+5] ={};
    maxBranchNum[0] = 1;
    maxBranchNum[0] -= A[0];
    
    for(int i=1;i<=N;i++){
        maxBranchNum[i] = maxBranchNum[i-1]*2 -A[i];
        if(maxBranchNum[i]<0){
            cout << -1 << endl;
            return;
        }
        if(maxBranchNum[i]>INF){
            maxBranchNum[i] = INF;
        }
        // cerr <<"max=" <<maxBranchNum[i] << endl;
    }
    
    ll ans =A[N];
    ll childNum = A[N];
   
    for(int i=N-1;i>=0;--i){
        // cerr <<"i="<<i <<"child= "<< childNum<<"max=" << maxBranchNum[i]<<endl; 
        childNum = min(childNum,maxBranchNum[i]);
        childNum += A[i];
        ans += childNum;
    }
    cout << ans << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N+1);
    for(int i = 0 ; i < N+1 ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


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

class Main{
    public static void main(String args[])throws IOException{
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
          String[] num = br.readLine().split(" ");
          int A = Integer.parseInt(num[0]);
          int B = Integer.parseInt(num[1]);

          System.out.println(A*B);
        }
    }
}

Measured memory_bytes: 32600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<ll> a(n), cnt(n, 0);
    rep(i, n) cin >> a[i];
    vector<ll> ans;
    rrep(i, n) {
        ll cur = i, sum = 0;
        while(cur < n) {
            sum += cnt[cur];
            cur += i + 1;
        }
        if (sum % 2 != a[i]) {
            cnt[i]++;
            ans.push_back(i + 1);
        }
    }
    printf("%lld\n", sz(ans));
    rep(i, sz(ans)) printf("%lld%s", ans[i], (i == (sz(ans) - 1)) ? "\n" : " ");
    return 0;
}


Measured memory_bytes: 5108
import java.util.*;
import java.io.*;
import java.util.function.*;

class Main {
    static In in = new In();
    static Out out = new Out();
    static long mod = 1000000007;
    static long inf = 0xfffffffffffffffL;

    void solve() {
        long n = in.nextLong();
        if (n % 2 == 0) {
            n /= 2;
            long ans = 0;
            long a = 5;
            while (a <= n) {
                ans += n / a;
                a *= 5;
            }
            out.println(ans);
        } else {
            out.println(0);
        }
    }

    public static void main(String[]$) {
        try {
            new Main().solve();
            out.flush();
        } catch (Throwable t) {
            out.flush();
            t.printStackTrace();
        }
    }
}

class In {
    private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    char[][] nextCharArray(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }
}

class Out {
    private static PrintWriter out = new PrintWriter(System.out);

    void println(Object... a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (Object obj : a) {
            joiner.add(String.valueOf(obj));
        }
        out.println(joiner);
    }

    void flush() {
        out.flush();
    }
}


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

int main(){
	for(int n; cin>>n&&n;){
		vector<int> l(n+1);
		for(int i=0; i<=n; i++) cin>>l[i];
		for(int s=0; s<=n; s++){
			int diff=INT_MAX;
			for(int i=s?1:2; i<=n; i++){
				if(i==s) continue;
				int be = i==s+1 ? 2 : 1;
				if(diff==INT_MAX){
					diff = l[i]-l[i-be];
				}else if(diff != l[i]-l[i-be]){
					goto BREAK;
				}
			}
			cout<<l[s]<<endl;
			break;
			BREAK:;
		}
	}
}

Measured memory_bytes: 3104
from sys import stdin
input = stdin.readline

D = {'a':0, 'b':1, 'c':2, 'd':3, 'e':4,
    'f':5, 'g':6, 'h':7, 'i':8, 'j':9,
    'k':10,'l':11,'m':12,'n':13,'o':14,
    'p':15,'q':16,'r':17,'s':18,'t':19,
    'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}

W = list(input().strip())

T = [0] * 26

for w in W:
    T[D[w]] += 1

b = True
for i in range(26):
    if T[i]%2 == 1:
        b = False
        break
if b == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9056
n = int(input())
a = []
for i in range(n):
  dmy = int(input())
  a.append(dmy)
  
a_max = a.index(max(a))
a.sort()
for i in range(n):
  if i==a_max:
    print("{}".format(a[-2]))
  else:
    print("{}".format(a[-1]))

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

#define ll long long
#define pb push_back
#define mp make_pair
#define um unordered_map
#define us unordered_set
#define mod 1000000007
#define all(x) x.begin(),x.end()

using namespace std;

int solve(vector<int> a,int n){
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	int n=s.length();
	if(s[n-1] == 's'){
		s+="es";
	}
	else{
		s+='s';
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 3644
#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 << "Balanced" << endl;
	else cout << "Right" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,j,k,m,n,b,f,r,v,ara[4][3][10];
    for(i=0;i<4;i++){
        for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                ara[i][j][k]=0;
            }
        }
    }
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        ara[b-1][f-1][r-1]+=v;
    }
    for(i=0;i<4;i++){
        for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                printf(" %d",ara[i][j][k]);
            }
            printf("\n");
        }
        if(i<3)
            printf("####################\n");
    }
return 0;
}


Measured memory_bytes: 2040
import sys
import math


def len(lhs, rhs):
    return math.sqrt((lhs[0] - rhs[0]) ** 2 + (lhs[1] - rhs[1]) ** 2)


def solve(n: int, cities):
    sum = 0
    for i1, city1 in enumerate(cities):
        for i2, city2 in enumerate(cities):
            if i1 != i2:
                sum += len(city1, city2)
    return sum / n


def main():
    inputs = list(sys.stdin)
    n = int(inputs.pop(0))
    cities = [[int(n) for n in s.split(" ")] for s in inputs]
    print(solve(n, cities))


main()


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

int main() {
	char x[2][3];
	int i, j;
	for (i = 0; i < 2; i++) {
		for (j = 0; j < 3; j++) {
			cin >> x[i][j];
		}
	}
	
	if (x[0][0] == x[1][2] && x[0][1] == x[1][1] && x[0][2] == x[1][0]) {
		cout << "YES";
	}
	else { cout << "NO"; }

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(arr) (int)(arr).size()
#define rng(arr) arr.begin(), arr.end()
#define show(x) cout << #x << " = " << x << endl;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
typedef long long int ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

int wa(string s) {
  int ret = 0;
  rep(i, sz(s)) ret += s[i] - '0';
  return ret;
}

void Main() {
  Cin(string, s);

  int ans = 0;
  rep(i, sz(s)) {
    rep(j, 10) {
      string ss(sz(s), '9');
      ss[i] = j + '0';
      if (s >= ss) {
        ans = max(ans, wa(ss));
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 400005;
using lint = long long;
using pi = pair<int, int>;

int n, a[MAXN];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		a[i] -= i;
	}
	sort(a, a + n);
	lint ret = 0;
	for(int i=0; i<n-1-i; i++) ret += a[n-1-i] - a[i];
	cout << ret << endl;
}


Measured memory_bytes: 1024
/*
 ▓█████▄  ▄████▄  ▓██   ██▓ ██▓███   ██░ ██ ▓█████  ██▀███
▒██▀ ██▌▒██▀ ▀█   ▒██  ██▒▓██░  ██▒▓██░ ██▒▓█   ▀ ▓██ ▒ ██▒
 ░██   █▌▒▓█    ▄   ▒██ ██░▓██░ ██▓▒▒██▀▀██░▒███   ▓██ ░▄█ ▒
 ░▓█▄   ▌▒▓▓▄ ▄██▒  ░ ▐██▓░▒██▄█▓▒ ▒░▓█ ░██ ▒▓█  ▄ ▒██▀▀█▄
 ░▒████▓ ▒ ▓███▀ ░  ░ ██▒▓░▒██▒ ░  ░░▓█▒░██▓░▒████▒░██▓ ▒██▒
  ▒▒▓  ▒ ░ ░▒ ▒  ░   ██▒▒▒ ▒▓▒░ ░  ░ ▒ ░░▒░▒░░ ▒░ ░░ ▒▓ ░▒▓░
  ░ ▒  ▒   ░  ▒    ▓██ ░▒░ ░▒ ░      ▒ ░▒░ ░ ░ ░  ░  ░▒ ░ ▒░
  ░ ░  ░ ░         ▒ ▒ ░░  ░░        ░  ░░ ░   ░     ░░   ░
    ░    ░ ░       ░ ░               ░  ░  ░   ░  ░   ░
  ░      ░         ░ ░
*/
//focus less on how much problem you should solve within a fixed time and focus more on getting the problem solved and
//learning something from it
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define per(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define sedes set <ll, greater <ll> >
#define seasc set <ll>
#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define MOD 1000000007
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define umap unordered_map<ll, ll>
#define map map<ll, ll>
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define mems(a, i) memset(a, i, sizeof(a))
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define deba(a) cout << #a << " " << a << endl;
int main()
{
	fast;
#ifndef ONLINE_JUDGE
	freopen("/home/kushagra/Desktop/Kushagra/input.txt", "r", stdin);
	freopen("/home/kushagra/Desktop/Kushagra/output.txt", "w", stdout);
#endif
	ll x, y, z, k;
	cin >> x >> y >> z >> k;

	ll a[x], b[y], c[z];
	rep(i, 0, x)
	cin >> a[i];
	rep(i, 0, y)
	cin >> b[i];
	rep(i, 0, z)
	cin >> c[i];
	vi sums;

	sort(a, a + x);
	sort(b, b + y);
	sort(c, c + z);

	rep(i, 0, x)
	{
		rep(j, 0, y)
		{
			sums.pb(a[i] + b[j]);
		}
	}
	sort(all(sums), greater<>());
	sums.resize(k);

	int sz = 0;
	vi ans;
	rep(i, 0, sums.size())
	{
		rep(j, 0, z)
		{
			ans.pb(sums[i] + c[j]);
		}
	}


	sort(all(ans), greater<>());

	rep(i, 0, k)
	cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 44040
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;



int main(){
    int N,H,W;cin >> N >> H >> W;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int a,b;cin >> a >> b;
        ans += (H<=a)*(W<=b);
    }
    cout << ans << endl;
    return 0;
}



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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

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(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    COMinit();
    int N; cin >> N;
    int cnt[N+1] = {};
    int fst, snd;
    int A[N+1];
    rep(i, N+1){
        int a; cin >> a;
        cnt[a]++;
        A[i] = a;
        if(cnt[a] == 2){
            snd = i;
            rep(j, i) if(A[j] == A[i]) fst = j; 
        }
    }

    for(int k = 1; k <= N+1; k++){
        ll res = COM(N+1, k);
        //fstの左側と右側から合わせてk-1個取る
        ll choice = fst + (N - snd);
        res = (res - COM(choice, k-1)) % MOD;
        if(res < 0) res += MOD;
        cout << res << "\n";
    }
    return 0;
}


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

using namespace std;

unsigned long long int power(int times)
{
    unsigned long long int pow = 1;
    for (int i = 0 ; i < times ; i++)
        pow *= 26;
    return pow;
}

int main()
{
    unsigned long long int n, mini = 1, maxi = 26, diff, sub;
    int i;
    cin >> n;
    for (i = 1 ; i <= 15 ; i++)
    {
        if (n >= mini && n <= maxi)
            break;
        mini = maxi + 1;
        maxi = maxi + power(i+1);
    }
    vector<int> digits(i, 0);
    diff = n - mini;
    sub = diff / 26;
    digits[0] = diff - 26 * sub;
    for (int j = 1 ; sub > 0 ; j++)
    {
        if (sub < 26)
        {
            digits[j] = sub;
            break;
        }
        else
        {
            diff = sub;
            sub /= 26;
            digits[j] = diff - 26 * sub;
        }
    }
    for (int j = digits.size()-1 ; j >= 0 ; j--)
    {
        cout << char('a' + digits[j]);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3628
from itertools import accumulate
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
acc = list(accumulate(range(N+1)))
ans = 0
for k in range(K, N+2):
    minSum = acc[k-1]
    maxSum = acc[N] - (acc[N-k] if k != N+1 else 0)
    ans += maxSum - minSum + 1
    ans %= MOD
print(ans)

Measured memory_bytes: 19304
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

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

const int MAXT = 51, MAXP = 11, MAXR = 500,MAXTIME = 10800;

int tid,pid,atime;
int t,p,r;
string message ;
int ac[MAXT], wa[MAXT][MAXP], pena[MAXT];
bool used[MAXT];
typedef pair<int, int> pp;

int main()
{
    while(cin >> t >> p >> r && t)
    {
        memset(ac, 0, sizeof(ac));
        memset(wa, 0, sizeof(wa));
        memset(used, false , sizeof(used));
        memset(pena, 0, sizeof(pena));
        
        REP(r)
        {
            cin >> tid >> pid >> atime >> message;
            if(message == "WRONG")
                wa[tid][pid]++;

            else
            {
                ac[tid]++;
                pena[tid] += (wa[tid][pid] * 1200 + atime);
            }
        }
        rep(j,t)
        {
            int topacc = -1, topp = 100000,top = 0;
            
            onen(i,t)//取り出すことをt回繰り返す
            {
                if(!used[i])
                {
                    if(topacc < ac[i] || (topacc == ac[i] && topp > pena[i]))
                    {
                        top = i;
                        topacc = ac[i];
                        topp = pena[i];
                    }
                }
            }
            used[top] = true;
            cout << top << " " << topacc << " " << topp << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 924
#include "bits/stdc++.h"

using namespace std;

//int N,M,K,L,R,H,W;
long long int N,M,K,L,R,H,W;

constexpr long long int MOD=1000000007;
//constexpr  int MOD=1000000007;
//constexpr int MOD=998244353;
//constexpr long long int MOD=998244353;

constexpr long double EPS=1e-8;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>N>>K;
	vector<int>v(N);
	for(auto &i:v)cin>>i;
	vector<int>w;
	for(int i=1;i<N;i++)w.push_back(v[i]-v[i-1]);
	sort(w.begin(),w.end());
	reverse(w.begin(),w.end());
	int ans=K;
	while(w.size()>K-1){
		ans+=w.back();
		w.pop_back();
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3944
#include<stdio.h>
int main(void){
int n,m,x;  //n:ほんの数　//m:アルゴリズムの数
  scanf("%d%d%d",&n,&m,&x);
  int c[n];
  int a[n][m];
  for(int i=0;i<n;i++){
    	scanf("%d",&c[i]);
    	for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
        }
  }
  long money=0,min=10000000,skill[m];
 int flag2=0;
  for(int i=0;i<(1<<n);i++){
    int flag=0;
    money=0;
   	for(int l=0;l<m;l++){		//初期化
	skill[l]=0;
    }
	for(int j=0;j<n;j++){
	if(i&(1<<j)){		//j冊目の本による効果を計算
      money+=c[j];		//金額を加算
      for(int k=0;k<m;k++){
        skill[k]+=a[j][k];
      }
    }
    }//あるパターンにおける計算終了
    for(int s=0;s<m;s++){
      	if(skill[s]<x)flag=1;
    }
    if(!flag&&min>money){
      min=money;
      flag2=1;
  }
  }
    if(!flag2)printf("-1");
    else printf("%ld",min);
    return 0;
  }

Measured memory_bytes: 1736
def Check_Year(year):
    if str(year).isdecimal() :
        return 1
    else:
        return 0

def Check_Month(month):
    if 0 < month < 13:
        return 1
    else:
        return 0

input_data = list(input())
head_chrs = int(input_data[0] + input_data[1])
# print('head: ', head_chrs)
tail_chrs = int(input_data[2] + input_data[3])
# print('tail: ', tail_chrs)

# print(input_data)

# check for YYMM format
result1 = Check_Year(head_chrs) + Check_Month(tail_chrs)
# print('result1: ' , result1)
# Check for MMYY format
result2 = Check_Year(tail_chrs) + Check_Month(head_chrs)
# print('result2: ' , result2)

if result1 == 2 and result2 == 2 :
    print('AMBIGUOUS')
elif result1 == 2 and result2 != 2 :
    print('YYMM')
elif result1 != 2 and result2 == 2 :
    print('MMYY')
else :
    print('NA')



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

#define MAX_N 200001

void dfs(int node, int parent, int *tree[], int child_num[], int node_num[]){
  int child;
  for(int i = 0; i < child_num[node]; i++){
    child = tree[node][i];
    if(child != parent){
      node_num[child] += node_num[node];
      dfs(child, node, tree, child_num, node_num);
    }
  }
}

void input_node(int a, int b, int *tree[], int tree_size[], int child_num[]){
  if(tree_size[a] == 0){
    tree[a] = (int *)malloc(sizeof(int));
    tree_size[a] = 1;
  }else if(child_num[a] == tree_size[a]){
    tree[a] = (int *)realloc(tree[a],sizeof(int)*tree_size[a]*2);
    tree_size[a] *= 2;
  }
  tree[a][child_num[a]++] = b;
}

int main(void){

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

  int *tree[MAX_N];
  int tree_size[MAX_N] = {};
  int child_num[MAX_N] = {};

  int a,b;
  for(int i = 0; i < n-1; i++){
    scanf("%d %d", &a, &b);
    input_node(a, b, tree, tree_size, child_num);
    input_node(b, a, tree, tree_size, child_num);
  }

  int p,x;
  int node_num[MAX_N] = {};
  for(int i = 0; i < q; i++){
    scanf("%d %d", &p, &x);
    node_num[p] += x;
  }

  dfs(1, 0, tree, child_num, node_num);

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

  return 0;
}

Measured memory_bytes: 31232
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstdlib>
#include <ctime>

using namespace std;

//#define HOME
void jakos() {
#ifdef HOME
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

#define endl '\n'
#define int long long
typedef long long ll;

const int mod = 1e9 + 7;
const int base = 179;
const int INF = 1e18;
const int N = 1e5 + 7;

signed main() {
    jakos();

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    double eps = 1e-6;
    vector<double> m(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        m[i] = ((double)a[i] + 1) / 2;
    }
    vector<double> pref(n + 1);
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i-1] + m[i-1];
    }
    double mx = 0;
    for (int i = k; i <= n; i++) {
        if (mx + eps < pref[i] - pref[i - k]) {
            mx = pref[i] - pref[i - k];
        }
    }

    printf("%.8lf", mx);

    return 0;
}

Measured memory_bytes: 4992
#include <cstdio>
#include <algorithm>

using namespace std;

long long x[100002];
int v[100002];
long long a[100002];
long long b[100002];

int main() {
    int n, i;
    long long c, ans = 0;
    
    scanf("%d %lld", &n, &c);
    
    x[0] = 0;
    v[0] = 0;
    
    for (i = 1; i <= n; i++) scanf("%lld %d", &x[i], &v[i]);
    
    x[n + 1] = c;
    v[n + 1] = 0;
    
    for (i = 1; i <= n; i++) a[i] = a[i - 1] + v[i] - (x[i] - x[i - 1]);
    for (i = 1; i <= n; i++) a[i] = max(a[i], a[i - 1]);
    
    for (i = n; i >= 1; i--) b[i] = b[i + 1] + v[i] - (x[i + 1] - x[i]);
    for (i = n; i >= 1; i--) b[i] = max(b[i], b[i + 1]);
    
    for (i = 1; i <= n; i++) {
        ans = max(ans, a[i]);
        ans = max(ans, a[i] - x[i] + b[i + 1]);
        ans = max(ans, b[i]);
        ans = max(ans, b[i] - (c - x[i]) + a[i - 1]);
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 2944
#include "bits/stdc++.h"

#define REP(i,num) for(ll i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int N=in();
	auto A=vecin(N),B=vecin(N),C=vecin(N);
	sort(ALL(A));
	sort(ALL(B));
	sort(ALL(C));

	ll S=0;
	REP(i,N){
		auto resA = lower_bound(ALL(A),B[i]);
		auto resC = lower_bound(ALL(C),B[i]+1);
		S += distance(A.begin(),resA)*distance(resC,C.end());
	}
	out(S);
	return 0;
}


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

using namespace std;

#define FOR(v, b, e)   for (int v = (b); v < (e); ++v)

typedef long long           ll;
typedef unsigned long long  ull;

ll calc (int a0, vector<int>& a) {
	ll total  = a0;
	ll result = 0;
	FOR (i, 1, a.size()) {
		if (total < 0) {
			total += a[i];
			if (total <= 0) {
				result += 1 - total;
				total   = 1;
			}
			continue;
		}

		total += a[i];
		if (total >= 0) {
			result += total + 1;
			total   = -1;
		}
	}
	return result;
}

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

	int N;
	cin >> N;

	vector<int> a(N);
	for (auto& ai : a) cin >> ai;

	ll result = 0;
	if (a[0] == 0) {
		auto result1 = calc( 1, a) + 1;
		auto result2 = calc(-1, a) + 1;
		result       = min(result1, result2);
	} else {
		auto result1 = calc(a[0], a);
		auto result2 = calc(   1, a) + abs( 1 - a[0]);
		auto result3 = calc(  -1, a) + abs(-1 - a[0]);
		result       = min(min(result1, result2), result3);
	}

	cout << result << endl;
}

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


  int findSumOfDigits (int n) {
    int sum = 0;
    while (n > 0) {
      sum += n % 10;
      n /= 10;
    }
    return sum;
  }

int main(void) {
  int N, A, B;
  cin >> N >> A >>B;
  
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
      if (A <= findSumOfDigits (i) && findSumOfDigits (i) <= B ) {
        ans += i;
      }
    }
      
      cout << ans << endl;
  
}

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

char easytolower(char in) {
  if(in <= 'Z' && in >= 'A')
    return in - ('Z' - 'z');
  return in;
}

void solve(int n, int k, char s[]){
    s[k-1] = easytolower(s[k-1]);
    for(int i=0;i<n;i++){
        cout << s[i];
    }
    cout << endl;
}

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

}

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

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;


int main() {
	fast;
	cin.tie(0);
	lld a, b, c, d;
	cin >> a >> b >> c >> d;
	bool flag = false;
	if ((a <= 0 && b >= 0) || (c <= 0 && d >= 0)) flag = true;
	lld ans = max(a * c, max(a * d, max(b * c, b * d)));
	if (flag) ans = max(ans, 0ll);
	cout << ans << endl;
}








Measured memory_bytes: 3648
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
char in[210000];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	int L=9999999;
	int R=0;
	for(int i=0;i<n;i++){
		if(in[i]=='A'){L=i;break;}
	}
	for(int i=n-1;i>=0;i--){
		if(in[i]=='Z'){R=i;break;}
	}
	printf("%d\n",R-L+1);
}

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

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


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


template<typename T> 
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(Int i){
    T s=0;
    for(Int x=i;x<=n;x+=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x>0;x-=(x&-x))
      bit[x]+=a;
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<char> c(n*2);
  vector<Int>  a(n*2);
  for(Int i=0;i<n*2;i++) cin>>c[i]>>a[i];

  BIT<Int> bit1(n+10,0),bit2(n+10,0);
  vector<Int> rev1(n+1),rev2(n+1);
  for(Int i=0;i<n*2;i++){
    if(c[i]=='W'){
      rev1[a[i]]=bit1.sum(a[i]);
      bit1.add(a[i],1);
    }else{
      rev2[a[i]]=bit2.sum(a[i]);
      bit2.add(a[i],1);
    }    
  }
  
  const Int INF = 1e15;
  auto cost1=make_v<Int>(n+1,n+1);
  fill_v(cost1,0);
  for(Int j=0;j<n;j++){
    Int tmp=0;
    for(Int i=0;i<n*2;i++){
      if(c[i]=='W') cost1[a[i]][j]=tmp;
      else tmp+=a[i]>j;
    }
  }
  auto cost2=make_v<Int>(n+1,n+1);
  fill_v(cost2,0);
  for(Int j=0;j<n;j++){
    Int tmp=0;
    for(Int i=0;i<n*2;i++){
      if(c[i]=='B') cost2[a[i]][j]=tmp;
      else tmp+=a[i]>j;
    }
  }
  if(0){
    for(Int i=1;i<=n;i++)
      for(Int j=0;j<n;j++)
	cout<<i<<" "<<j<<":"<<cost1[i][j]<<" "<<cost2[i][j]<<endl;
  }
  auto dp=make_v<Int>(n+1,n+1);
  fill_v(dp,INF);
  dp[0][0]=0;
  for(Int i=0;i<=n;i++){
    for(Int j=0;j<=n;j++){
      //cout<<i<<" "<<j<<":"<<dp[i][j]<<endl;
      if(i<n) chmin(dp[i+1][j],dp[i][j]+cost1[i+1][j]+rev1[i+1]);
      if(j<n) chmin(dp[i][j+1],dp[i][j]+cost2[j+1][i]+rev2[j+1]);
    }
  }
  
  cout<<dp[n][n]<<endl;
  return 0;
}


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

using namespace std;

int main()
{
    long long a,sum,sum2,sum3;
    cin>>a;
    sum= a/500;
    sum2= a%500;
    sum3 = sum2/5;
    cout<<sum*1000+sum3*5<<endl;


    return 0;
}

Measured memory_bytes: 3644
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
d=Counter(a)
s=sum(a)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  t=d[b]
  d[b]=0
  s-=t*b
  d[c]+=t
  s+=t*c
  print(s)
  # t=d[b]
  # d[b]=0
  # d[c]+=t

# ans=0
# for k,v in d.items():
#   ans+=k*v
# print(ans)



Measured memory_bytes: 94000
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>     //by  @山?叶??     A
#include<cstdlib>
#include<cmath>
#include<string>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
double dinf=99999999.9, mm=1e-8;
const int N=10008,inf=0x3f3f3f3f;
ll gcd(ll x,ll y)
{
    if(x%y==0)
        return y;
    else
        return gcd(y,x%y);
}
int main()
{
    ll a,b;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        printf("%lld ",gcd(a,b));
        ll k,ans=1;
        while(k=gcd(a,b),k!=1)
        {
           ans*=k;
           a/=k;b/=k;
        }
        ans=ans*a*b;
        printf("%lld\n",ans);
    }

    return 0;
}

Measured memory_bytes: 3148
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
#define INF 168435450

typedef struct node{
 int flg;
 int cost;
}node;

typedef struct edge{
 int p_id;
 int cost;
 struct edge *next;
}edge;


edge* makecell(int v,int cost){
edge* new;

new=malloc(sizeof(edge));
new->p_id=v;
new->cost=cost;
new->next=NULL;

return new;

}

void insert(edge* E[],int x,edge* new){
edge **p;

p=&E[x];

while((*p)!=NULL)p=&((*p)->next);

(*p)=new;


return;
}

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


int min_idx(node N[],int n){
int idx;
int i;
int mini=268435450;

for(i=0;i<n;i++){
 if(N[i].flg==0 && N[i].cost<mini){
   mini=N[i].cost;
   idx=i;
 }
}

return idx;
}



int main(){
int n,x,y,d;
int i,j,k,u;
node N[MAX];
edge *E[MAX];
edge *new;
edge *p;

scanf("%d",&n);

for(i=0;i<n;i++){
 N[i].flg=0; 
 N[i].cost=INF;
 E[i]=NULL;
}



for(i=0;i<n;i++){
 scanf("%d %d",&x,&k);
 for(j=0;j<k;j++){
  scanf("%d %d",&y,&d);
  new=makecell(y,d);
  insert(E,x,new);
 }
}


N[0].cost=0;

for(i=0;i<n;i++){
 u=min_idx(N,n);


 if(N[u].flg==0){
    N[u].flg=1;
    
    p=E[u];
    while(p!=NULL){
      j=p->p_id;
      N[j].cost=min(N[j].cost,N[u].cost+p->cost);
      p=p->next;
    }
    
 }

}


for(i=0;i<n;i++)
 printf("%d %d\n",i,N[i].cost);


return 0;
}


Measured memory_bytes: 17340
#include <iostream>
#include <vector>
#include <map>

using namespace std;
#define int long long

signed main(){
  int ans = 0;
  int n, m;
  cin >> n >> m;
  vector<int> A(n);
  for(int i = 0; i < n; i++){
    cin >> A[i];
  }
  vector<int> B(n+1);
  B[0]=0;
  map<int, int> C;
  C[0]=1;
  for(int i = 0; i < n; i++){
    B[i+1]=(B[i]+A[i]) % m;
    C[B[i+1]]++;
  }
  
  for(auto m: C){
    ans += (m.second -1) * m.second / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,k;
  cin>>n>>k;
  set<ll> se;
  map<ll,ll> ma;
  for(ll i=0;i<n;i++){
    ll a,b;
    cin>>a>>b;
    ma[a]+=b;
    se.insert(a);
  }
  ll c=0;
  for(ll s:se){
    c+=ma[s];
    if(c>=k){
      cout<<s;
      return 0;
    }
  }
}

Measured memory_bytes: 7168
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
lint n, m;
lint arr[10000];

int main(){
    
    cin >> n >> m;
    priority_queue <lint> q;
    for(int i=0; i<n; i++){
        lint temp;
        cin >> temp;
        q.push(temp);
    }
    for(int i=0; i<m; i++){
        lint temp = q.top();
        q.pop();
        q.push(temp/2);
    }
    lint cntr = 0;
    for(int i=0; i<n; i++){
        cntr += q.top();
        q.pop();
    }
    cout << cntr;
    return 0;
}


Measured memory_bytes: 1400
#include <stdio.h>
int main(){
        int A[4],B[4],h=0,b=0,i,j;
        while(scanf("%d%d%d%d", &A[0], &A[1], &A[2], &A[3]) != EOF)
        {
                h=b=0;
                scanf("%d%d%d%d", &B[0],&B[1],&B[2],&B[3]);
                for(i=0;i<4;i++)
                        for(j=0;j<4;j++)
                        {
                                if(i==j && A[i] == B[j])
                                                h++;
                                else if(A[i] == B[j])
                                                b++;
                        }
                printf("%d %d\n",h,b);
        }
return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
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));
}

ll mod(ll x){
	return x%MOD;
}

//a,b x
int main(){
	string s; cin>>s;
	vector<vector<ll>> dp(s.sz+1,vector<ll>(4,0));
	dp[s.sz][3]=1;
	rep(i,3) dp[s.sz][i]=0;
	
	for(int i=s.sz-1;i>=0;i--){
		if(s[i]=='?') dp[i][3]=(3*dp[i+1][3])%MOD;
		else dp[i][3]=dp[i+1][3];

		rep(j,3){
			ll m1=1,m2=0;
			if(s[i]=='?') m1=3;
			if(s[i]=='?' || s[i]-'A'==j) m2=1;
			dp[i][j]=((m1*dp[i+1][j])%MOD+m2*dp[i+1][j+1])%MOD;
		}
	}
	cout<<dp[0][0];
}

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

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#ifdef LOCAL
#define dmp(x) cerr << __LINE__ << " " << #x << " " << x << endl
#else
#define dmp(x) void(0)
#endif

template <class t, class u>
void chmax(t &a, u b)
{
  if (a < b)
    a = b;
}
template <class t, class u>
void chmin(t &a, u b)
{
  if (b < a)
    a = b;
}
const int mod = 1000000007;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};
struct combination
{
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1)
  {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
      fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i)
      ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k)
  {
    if (k < 0 || k > n)
      return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;

using vi = vc<int>;
int gcd(int a, int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
int lcm(int a, int b)
{
  return (a * b) / gcd(a, b);
}

int main()
{
  float n, m,k;
  cin >> n >> m >>k;
  cout <<ceil(k/max(n,m))<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
int main(){
	int N,t,f;
	scanf("%d",&N);
	for(t=N,f=N;;){
		t&=-t;
		f^=t;
		if(!f)break;
		N=f;
		t=N;
	}
	printf("%d",N);
} 

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

ll dp[114514][4];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	pii q[4];
	ll n;
	REP(i, 4){
		cin>>q[i].first;
		q[i].second=(1<<i);
	}
	cin>>n;
	ll m=n*4;
	pii x[4];
	REP(i, 4){
		x[i]=pii(q[i].first*(8>>i), i);
	}
	sort(x, x+4);
	ll ans=0;
	int cnt=0;
	while(m>0){
		ans+=(m/q[x[cnt].second].second)*q[x[cnt].second].first;
		m=m%q[x[cnt].second].second;
		++cnt;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <functional>

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

int main()
{
	for(;;) {
		int n;
		scanf("%d", &n);
		if(n==0) return 0;
		vector<int> emp[30];
		rep(i, n) {
			int m;
			scanf("%d", &m);
			rep(j, m) {
				int d;
				scanf("%d", &d);
				emp[d-1].push_back(i);
			}
		}
		vector<long long> ps;
		rep(i, n) ps.push_back(((long long)1)<<i);
		long long g=(((long long)1)<<n)-1;
		int min = -1;
		rep(d, 30) {
			long long c = 0;
			rep(i, emp[d].size()) c |= ps[emp[d][i]];
			if(c==g) {
				min = d+1;
				break;
			}
			else {
				rep(i, emp[d].size()) ps[emp[d][i]] = c;
			}
		}
		printf("%d\n", min);
	}
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();

            int a = input[0];
            int b = input[1];

            Console.WriteLine(Math.Max(Math.Max(a * b, a + b), a - b));
            
        }
    }
}

Measured memory_bytes: 13268
n = int(input())
#a, b = map(int, input().split())
#l = list(map(int, input().split()))
#s = input()

acCnt = 0
waCnt = 0
tlCnt = 0
reCnt = 0

for i in range(n):
    s = input()
    if s == "AC":
        acCnt = acCnt + 1
    elif s == "WA":
        waCnt = waCnt + 1
    elif s == "TLE":
        tlCnt = tlCnt + 1
    else:
        reCnt = reCnt + 1

print ("AC x",acCnt)
print ("WA x",waCnt)
print ("TLE x",tlCnt)
print ("RE x",reCnt)







Measured memory_bytes: 9156