akhauriyash/Code-Regression huggingface dataset:
// #include <bits/stdc++.h>
#include<climits>
#include<cmath>
#include<cstdio>
#include<deque>
#include<map>
#include<set>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<string>
#include<tuple>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define pt pop_front
#define pk pop_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
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;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
long N,M,B,C,n;
vector<long>A;
cpp_int sum;
map<long,long,greater<long>>m;
vector<pair<long,long>>D;
inline void solve(void){
  in(N,M);
  A.rs(N);
  rep(i,N){
    in(A[i]);
    m[A[i]]++;
  }
  rep(i,M){
    in(B,C);
    m[C]+=B;
  }
  for(auto e:m){
    if(n+e.sd<=N){
      sum+=e.ft*min(e.sd,N);
      n+=min(e.sd,N);
    }else{
      sum+=e.ft*(N-n);
      break;
    }
  }
  out(sum);
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n';

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int h, w;cin>>h>>w;
    string s[h];
    ll dp[h][w];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 0; i < h; ++i){
        cin>>s[i];
        for(int j = 0; j < w; ++j){
            if(i) dp[i][j] += dp[i-1][j];
            if(j) dp[i][j] += dp[i][j-1];
            if(s[i][j]=='#') dp[i][j] = 0;
            dp[i][j]%=(ll)1e9 + 7;
        }
    }
    cout<<dp[h-1][w-1]<<endl;
    return 0;

}

Measured memory_bytes: 12524
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    if op == '?':
        quit()
    elif op == '+':
        c=a+b
    elif op == '-':
        c=a-b
    elif op == '*':
        c=a*b
    elif op == '/':
        c=a//b
    print(c)

Measured memory_bytes: 7672
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main() {
    int n,x,y;
    cin >> n >> x >> y;
    x--;y--;
    vector<vector<int>>dist(n,vector<int>(n,-1));
    for(int s = 0;s<n;s++) {
        dist[s][s] = 0;
        queue<int>q;
        q.push(s);
        while(!q.empty()) {
            int v = q.front();q.pop();
            vector<int>nvs;
            if(v == 0) nvs.push_back(v+1);
            if(v > 0 && v<n-1) nvs.push_back(v-1);nvs.push_back(v+1);
            if(v == n-1) nvs.push_back(v-1);
            if(v == x) nvs.push_back(y);
            if(v == y) nvs.push_back(x);
            for(int nv : nvs) {
                if(dist[s][nv] != -1) continue;
                dist[s][nv] = dist[s][v] + 1;
                q.push(nv);
            }
        }
    }
    vector<int>cnt(n,0);
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<n;j++) {
            cnt[dist[i][j]]++; 
        }
    }
    for(int i = 1;i<n;i++) {
        cout << cnt[i]/2 << endl;
    }
}

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

int main(){
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  int x[N],y[M];
  for (int i=0;i<N;i++){
    cin>>x[i];
  }
  for (int j=0;j<M;j++){
    cin>>y[j];
  }
  sort(x,x+N,greater<int>());
  sort(y,y+M);
  bool flag=false;
  for (int z=-100;z<=100;z++){
    if (z>X&&z<=Y&&x[0]<z&&y[0]>=z){
      flag=true;
    }
  }
  if (flag==true){
    cout<<"No War";
  }
  else{
    cout<<"War";
  }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

def solve(N, S):
    x = 0
    res = 0
    for i in range(N):
        if(S[i]=="I"):
            x += 1
        else:
            x -= 1
        res = max(res, x)
        
    print(res)
    

if __name__ == '__main__':
    N = int(input())
    S = input()
    
    solve(N, S)

Measured memory_bytes: 2940
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    r, g, b, n = map(int, input().split())
    res = 0
    for i in range(n + 1):
        for j in range(n + 1):
            x = n - r * i - g * j 
            if x >= 0 and x % b == 0:
                res += 1
    print(res)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()


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

int main() {
    int N, C;
    cin >> N >> C;
    using P = pair<int, pair<int, int>>; // 時刻, イベントタイプ, チャンネル
    priority_queue<P, vector<P>, greater<P>> que;
    rep(i, N) {
        int s, t, c;
        cin >> s >> t >> c;
        s *= 2, t *= 2, --c;
        que.push(P(s, {0, c}));
        que.push(P(t, {1, c}));
    }
    int ans = 0, now = 0;
    vector<int> channel(C);
    while(!que.empty()) {
        auto p = que.top();
        que.pop();
        int t = p.first;
        int type, c;
        tie(type, c) = p.second;
        if(type) { // 終了クエリ
            if(--channel[c] == 0) --now;
        } else { // 開始クエリ
            if(channel[c]++ == 0) ++now;
        }
        ans = max(ans, now);
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 4980
#include<stdio.h>

int main(void)
{
  int N,c=0;
  scanf("%d",&N);
  int W[N],allsum=0;
  int N_=N;
  while(N_--)
  {
    scanf("%d",&W[c]);
    allsum+=W[c];
    c++;
  }
  c=0;
  N_=N;
  int sum1=0,sum2=allsum,gap,gap_min=allsum;
  while(N_--)
  {
    sum1+=W[c];
    sum2-=W[c];
    gap=sum2-sum1;
    if (gap<0)
    {
      gap=gap*(-1);
    }
    if (gap<gap_min) gap_min=gap;
    if (gap_min==0) break;
    c++;
  }
  printf("%d",gap_min);
}

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

int main() {
    int D, N;
    cin >> D >> N;

    int ans;

    if (N == 100){
        ans = pow(100, D) * (N + 1);
    } else {
        ans = pow(100, D) * N;        
    }

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

Measured memory_bytes: 256
N, M = map(int, input().split())
Keys = []
keys_set = set()

for m in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    c = [2 ** (ci - 1) for ci in c]
    Keys.append([a, sum(c)])
    keys_set |= set(c)


# 不可能判定
if len(keys_set) != N:
    print(-1)
    exit()


dp = [[float('inf')] * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i, (a, c) in enumerate(Keys):
    for bs in range(2 ** N):
        dp[i + 1][bs] = min(dp[i + 1][bs], dp[i][bs])
        dp[i + 1][bs | c] = min(dp[i][bs | c], dp[i + 1][bs | c], dp[i][bs] + a)

ans = float('inf')
for d in dp:
    ans = min(ans, d[-1])
print(ans)


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

int main(){
    ll x,p=100,k=0;
    cin>>x;
    while(1){
        p+=p/100;
        k++;
        if(p>=x){
            break;
        }
    }
    cout << k;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end(),greater<int>());
    ll ans = 0;
	for(int i=1;i<n;i++){
    	ans += a[i/2];
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3984
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
void solve()
{
    ll n;
    cin>>n;
    vl a(n);
    forr(i, n)  cin>>a[i];
    sort(all(a));
    ll prod=1;
    forr(i, n)
    {
        if(prod*a[i]!=1000000000000000000&&prod>=ceil(1000000000000000000*1.0/(a[i]*1.0)))
        {
            //cout<<prod<<" "<<i<<endl;
            cout<<-1;
            return;
        }
        //cout<<prod<<" "<<ceil(1e18*1.0/(a[i]*1.0))<<endl;
        prod*=a[i];
    }
    cout<<prod;
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}

Measured memory_bytes: 4048
def actual(N, A):
    records = []

    for i, a in enumerate(A, start=1):
        record = dict(student_id=str(i), num_students=a)
        records.append(record)

    records_asc = sorted(records, key=lambda x: x['num_students'])

    return ' '.join([record['student_id'] for record in records_asc])


N = int(input())
A = list(map(int, input().split()))
print(actual(N, A))

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

int func(string s,string t){
    int ans=0;
    for(char c='a';c<='z';c++){
        bool left=false,right=false;
        for(int i=0;i<s.length();i++){
            if(s[i]==c) left=true;
        }
        for(int i=0;i<t.length();i++){
            if(t[i]==c) right=true;
        }
        if(left&&right) ans++;
    }
    return ans;
}

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

    int ans=0;
    for(int i=1;i<N;i++){
        int a=func(S.substr(0,i),S.substr(i));
        ans=max(a,ans);
    }
    cout<<ans<<endl;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;


int main() {
    int a, b, c;
    cin >> a >> b >> c;
    bool ans = (b - a == c - b) ? true: false;
    if (ans) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    X, Y = read_values()
    for a in range(X + 1):
        if Y == a * 2 + (X - a) * 4:
            print("Yes")
            return
    print("No")


if __name__ == "__main__":
    main()



Measured memory_bytes: 9948
N = int(input())
li = list(map(int,input().split()))
sum1 = 0
sum2 = 0
sum3 = 0
sum4 = 0
for i in range(N):
    sum1 += li[i]
    sum4 += li[i]
sum1 //= 2
for i in range(N):
    sum2 += li[i]
    if sum2 >= sum1:
        ans = min((sum2 - sum1 + abs(sum4-sum2-sum1)),((sum1-sum3)+sum4-sum3-sum1))
        break
    sum3 += li[i]
print(ans)

Measured memory_bytes: 87888
#pragma region

#ifdef LOCAL
#define debug cout
#else
#define debug \
    if (0) cout
#endif

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[ ";
    for (auto e : v) os << e << " ";
    return os << "]";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, set<T, V> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V, typename S>
ostream& operator<<(ostream& os, map<T, V, S> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, pair<T, V> x) {
    return os << "( " << x.first << ", " << x.second << " )";
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}

template <typename T, typename V>
istream& operator>>(istream& is, pair<T, V>& x) {
    return is >> x.first >> x.second;
}

void solve();

int main() {
#ifdef LOCAL
    freopen("data.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
}

#pragma endregion

void solve() {
    int n, w;
    cin >> n >> w;
    vector<pair<int, ll>> items(n);
    cin >> items;
    vector<ll> dp(w + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int k = w; k >= items[i].first; --k) {
            dp[k] = max(dp[k], items[i].second + dp[k - items[i].first]);
        }
    }
    cout << dp[w] << "\n";
}

Measured memory_bytes: 1024
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var max = 10;
    var sc = new Scanner(System.in);
    var n = sc.nextInt();
    var m = sc.nextInt();
    var q = sc.nextInt();
    var as = new int[q][4];
    for (int i = 0; i < q; i++) {
      as[i][0] = sc.nextInt() - 1;
      as[i][1] = sc.nextInt() - 1;
      as[i][2] = sc.nextInt();
      as[i][3] = sc.nextInt();
    }
    
    var arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = 1;
    }
    var i = 0;
    var count = 0;
    var answer = 0;
    while (true) {
      var point = 0;
      for (int k = 0; k < q; k++) {
        if (arr[as[k][1]] - arr[as[k][0]] == as[k][2]) {
          point += as[k][3];
        }
      }
      if (answer < point) {
        answer = point;
      }

      var j = n - 1;
      while (j >= 0 && arr[j] == m) {
        j--;
      }
      if (j < 0) {
        break;
      }
      arr[j]++;
      for (int k = j + 1;  k < n; k++) {
        arr[k] = arr[j];
      }
    }
    System.out.println(answer);
  }
}

Measured memory_bytes: 36628
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin>>s;
  int sum=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='1'){
      sum=sum+1;
    
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define ll long long int
#define loop(i,s,e) for(ll i=s; i<e; i++ )
#define endl '\n'
#define vll vector<ll>
#define pll pair<ll, ll>
#define ff first
#define ss second
using namespace std;

void alpha(){
	int D,M;
	cin>>M>>D;

	if(D<21 || M<4){
		cout<<0<<endl;
		return;
	}
	map<int, int> m;
	int ones, tens;

	for(int i=22; i<=D; i++){
		if(i%10!=0 && i%10!=1){
			ones=i%10;
			tens=(i-ones)/10;
			if(ones*tens<=M)m[ones*tens]++;
		}
	}

	int ans=0;

	map<int, int>::iterator itr=m.begin();

	for(itr=m.begin(); itr!=m.end(); itr++){
		ans+=itr->second;
	}

	cout<<ans<<endl;

	return;



}

int main(){

	alpha();

	return 0;

}

Measured memory_bytes: 256
// 深さ優先探索 dfs 753 755
#include <bits/stdc++.h>
using namespace std;

int N   = 0;
int ans = 0;

void dfs(string S) {
    if (stol(S) > N) return;
    bool has3 = S.find("3") != string::npos;
    bool has5 = S.find("5") != string::npos;
    bool has7 = S.find("7") != string::npos;
    if (has3 && has5 && has7) ans++;
    dfs(S + "3");
    dfs(S + "5");
    dfs(S + "7");
}

int main() {
    cin >> N;
    dfs("0");
    cout << ans << endl;
}

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

int main()
{
  int a, b;
  cin>>a>>b;
  if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  ll N;
  cin>>N;
  
  vector<string>S(N);
  vector<ll>date(26);
  rep(i,N){
    cin>>S[i];
  }

  rep(i,S[0].size()){
date[S[0][i]-'a']++;
  }


rep(i,N){
vector<ll>T(26);
  rep(j,S[i].size()){
    T[S[i][j]-'a']++;
  }
  
  rep(j,26){
if(date[j]>T[j]){
  date[j]=T[j];
}
  }
}


rep(i,date.size()){
  char s='a'+i;
  rep(j,date[i]){
    cout<<s;
  }
}

cout<<endl;
} 
    

 


Measured memory_bytes: 256
# include <iostream>
# include <string>
using namespace std;
int main()
{
	int t,n,p,q,r;
	p=0;
	q=0;
	r=0;
	n=0;
	cin>>t;
	for(int i=0; i<t; i++)
	{
		string s;
		cin>>s;
		if(s=="AC")
		{
			p=p+1;
		}
		if(s=="TLE")
		{
			q=q+1;
		}
		if(s=="WA")
		{
			r=r+1;
		}
		if(s=="RE")
		{
			n=n+1;
		}
	}
	cout<<"AC x "<<p<<endl;
	cout<<"WA x "<<r<<endl;
	cout<<"TLE x "<<q<<endl;
	cout<<"RE x "<<n<<endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;
const int vx[6] = {0,1,0,-1,1,-1};
const int vy[6] = {1,0,-1,0,1,1};




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

    int n,cc;
    cin >> n >> cc;
    vector<vector<int>> graph(n);
    rep(i,n-1){
        int x,y;
        cin >> x >> y;
        x--;y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    vector<int> c(n,0);
    rep(i,cc){
        int p,x;
        cin >> p >> x;
        p--;
        c[p] += x;
    }
    queue<int> q;
    q.push(0);
    vector<int> memo(n,-1);
    while(!q.empty()){
        int x = q.front();q.pop();
        memo[x] = 1;
        for(auto t : graph[x]){
            if(t == 0) continue;
            if(memo[t] != -1) continue;
            c[t] += c[x];
            q.push(t);
        }
    }
    rep(i,n){
        cout << c[i] << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 16372
#include<stdio.h>
#include<math.h>
#include<algorithm>
int main()
{
	int a[3];
	scanf("%d %d %d", &a[0], &a[1], &a[2]);
	std::sort(a, a + 3);
	int s = 0;
	for(int i=1;i<3;i++)
	{
		s += fabs(a[i] - a[i - 1]);
	}
	printf("%d", s);
	return 0;
}

Measured memory_bytes: 128
S=gets.chomp

a=[0]*2019
a[0]=1
t=0
b=1
S.chars.reverse_each do |c|
  d=c.to_i
  t=(t+d*b)%2019
  a[t]+=1
  b=b*10%2019
end
ret = a.reduce(0) {|s,e| s+e*(e-1)/2 }
puts ret


Measured memory_bytes: 24732
#![allow(unused)]

fn solve<R: std::io::BufRead>(mut sc: Scanner<R>) {
    let a: i64 = sc.get();
    let b: i64 = sc.get();
    let n: i64 = sc.get();

    if n < b {
        println!("{}", a * n / b );
    } else {
        println!("{}", a * (b - 1) / b);
    }
}

macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

//
// Based on EbTech's Scanner https://stackoverflow.com/q/56449027
//
struct Scanner<'a, R: std::io::BufRead> {
    reader: R,
    buf: String,
    iter: std::str::SplitWhitespace<'a>,
}

impl<'a, R: std::io::BufRead> Scanner<'a, R> {
    fn new(reader: R) -> Self {
        Self { reader, buf: String::new(), iter: "".split_whitespace() }
    }

    fn get<T: std::str::FromStr>(&mut self) -> T {
        if let Some(t) = self.iter.next() {
            return t.parse().ok().expect("Parse error")
        }
        self.buf.clear();
        self.reader.read_line(&mut self.buf).expect("I/O error");
        self.iter = unsafe { std::mem::transmute(self.buf.split_whitespace()) };
        self.get()
    }

    fn gets<T: std::iter::FromIterator<char>>(&mut self) -> T {
        use std::io::Read;
        assert_eq!(self.iter.next(), None);
        self.reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|&c| c.is_whitespace())
            .take_while(|&c| !c.is_whitespace())
            .collect()
    }
}

fn main() {
    let stdin = std::io::stdin();
    solve(Scanner::new(stdin.lock()));
}



Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int dp[1 << 13];
int w[1005],v[1005];

void init(int n){
	for(int i = 1;i <= n;++i) v[i] = 0;
	memset(dp,INF,sizeof(dp));
	return ;
}

int main()
{
    int x,k,n,m,s = 1;
    scanf("%d%d",&n,&m);
    init(m);
	
	s = (s << n)-1;
	for(int i = 1;i <= m;++i){
		scanf("%d%d",&w[i],&k);
		for(int j = 0;j < k;++j){
			scanf("%d",&x);
			v[i] |= (1 << (x-1));
		}
	}
	
	dp[0] = 0;
	for(int i = 1;i <= m;++i){
		for(int j = 0;j <= s;++j){
			dp[j | v[i]] = min(dp[j | v[i]],dp[j]+w[i]);
		}
	}

	printf("%d",dp[s] == INF ?-1 :dp[s]);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define nl '\n'
typedef long long ll;
typedef long double ld;
//////////////////////////////////////////////////////////////////////

map<int,int> mp,need;

int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  
  int n;cin>>n;
  for(int i=1;i<=n;i++){
    int d;cin>>d;
    mp[d]++;
  }
  
  int m;cin>>m;
  for(int i=1;i<=m;i++){
    int t;cin>>t;
    need[t]++;
  }

  bool yes = 1;
  for(auto&it:need){
    if( it.ss > mp[it.ff] ){
      yes = 0;
      break;
    }
  }
  cout << (yes ? "YES":"NO") << endl;
  
  return 0;
};


Measured memory_bytes: 19072
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const ll inf = (ll)4e18;
const double INF = 1e12, EPS = 1e-9;

int n, m, l, k[2000], s[100001];
ll sum[100001], dp[2001][2001];

int main(){
	scanf("%d%d%d", &n, &m, &l);
	rep(i, n) scanf("%d", k + i);
	rep(i, m) scanf("%d", s + i), sum[i + 1] = sum[i] + s[i];
	
	sort(k, k + n, greater<int>());
	rep(i, n + 1) rep(j, n + 1) dp[i][j] = inf;
	dp[0][0] = 0;
	
	ll ans = inf;
	rep(i, n) rep(j, i + 1) if(dp[i][j] < inf){
		int h = max(i, j) + 1;
		dp[h][j] = min(dp[j][h], dp[i][j] + (sum[k[i]] - sum[k[h] - 1]) / l);
		dp[h][i] = min(dp[h][i], dp[i][j] + (sum[k[j]] - sum[k[h] - 1]) / l);
	}
	rep(i, n) ans = min(ans, dp[n - 1][i] + (sum[k[i]] - sum[k[n - 1] - 1]) / l);
	cout << ans << endl;
	return 0;
}

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

MAX_V = 100

# デバッグ用の関数
def show(origami):
    for i in range(MAX_V):
        for j in range(MAX_V):
            print(origami[i][j], end = " ")
        print()
    print("--------------------------------------")

# 右に c だけ折り返す処理
def fold_a(origami, c):
    t = c
    for i in range(c):
        for j in range(MAX_V):
            origami[j][t+i] += origami[j][t-i-1]
            origami[j][t-i-1] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if j-c < 0 or MAX_V-1 < j-c:
                continue
            origami[i][j-c] = copy[i][j]


# 上に c だけ折り返す処理
def fold_b(origami, c):
    t = MAX_V - c -1
    for i in range(MAX_V):
        for j in range(c):
            origami[t-j][i] += origami[t+j+1][i]
            origami[t+j+1][i] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if i+c < 0 or MAX_V-1 < i+c:
                continue
            origami[i+c][j] = copy[i][j]



def main():
    while True:
        n, m, t, p = map(int, input().split())

        origami = [[0 for i in range(MAX_V)] for _ in range(MAX_V)]

        for i in range(n):
            for j in range(m):
                origami[-1-j][i] = 1

        if n == 0 and m == 0 and t == 0 and p == 0:
            break

        for _ in range(t):
            d, c = map(int, input().split())

            if d == 1:
                fold_a(origami, c)
            if d == 2:
                fold_b(origami, c)

        for _ in range(p):
            x, y = map(int, input().split())
            print(origami[MAX_V-y-1][x])

    return 0

main()


Measured memory_bytes: 5800
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using i64 = unsigned long long;
using namespace std;

const int maxn = 2e3;
int x, y, mx[3], val;
int sup[3];
vector< array<int, 3> > apple;

int main() {
  cin >> sup[0] >> sup[1] >> mx[0] >> mx[1] >> mx[2];
  for (int k = 0; k < 3; k++)
    for (int i = 0; i < mx[k]; i++) {
      cin >> val;
      apple.push_back({val, k});
    }
  
  sort(apple.begin(), apple.end());
  reverse(apple.begin(), apple.end());

  int sz[2] = {0};
  int sz_none[2] = {0};
  i64 sum = 0;

  for (int i = 0; i < apple.size(); i++) {
    char* name[3] = {"red", "green", "uncolored"};
    // printf("red: %d\ngreen: %d\n", sz[0], sz[1]);
    int &color = apple[i][1];
    int &cost = apple[i][0];
    if (color <= 1) {
      if (sz[color] + 1 > sup[color]) {
        // try moving a previous uncolored apple
        if (sz_none[color] > 0 & sz[color ^ 1] + 1 <= sup[color ^ 1]) {
          sz_none[color] -= 1;
          sz_none[color ^ 1] += 1;
          sz[color ^ 1] += 1; 
          // printf("moving from %s to %s\n", name[color], name[color ^ 1]);
          // printf("0add %d to %s\n", cost, name[color]);
          sum += cost;
        } else {
          continue;
        }
      } else {
        // printf("1add %d to %s\n", cost, name[color]);
        sz[color] += 1;
        sum += cost;
      }
    } else if (sz[0] + 1 <= sup[0]) {
      sz[0] += 1;
      sz_none[0] += 1;
      // printf("2add %d to %s\n", cost, name[0]);
      sum += cost;
    } else if (sz[1] + 1 <= sup[1]) {
      // printf("3add %d to %s\n", cost, name[1]);
      sz[1] += 1;
      sz_none[1] += 1;
      sum += cost;
    } else {
      break;
    }
    
  }  
  cout << sum << endl;
}

Measured memory_bytes: 8048
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

ll N, M;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  priority_queue<ll> pq;
  for (int i = 0; i < N; i++) {
    ll a;
    cin >> a;
    pq.push(a);
  }

  for (int i = 0; i < M; i++) {
    ll a = pq.top();
    pq.pop();
    pq.push(a / 2);
  }

  ll ans = 0;
  while (!pq.empty()) {
    ll a = pq.top();
    pq.pop();
    ans += a;
  }

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

Measured memory_bytes: 1400
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll PowMod(ll N,ll P,ll M){
    ll ans = 1;
    while(P >= 1){
        if(P % 2)ans = ans * N % M;
        N = N*N %M;
        P /= 2;
    }
    ans %= M;
    return ans;
}

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

    ll ans = PowMod(10, N, MOD) - 2 * PowMod(9, N, MOD) + PowMod(8, N, MOD);
    if(ans < 0) ans = (MOD - (-ans%MOD))%MOD;
    else ans %= MOD;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int fiveCnt = 0;
        int sevenCnt = 0;
        for (int i = 0; i < 3; i++) {
            int a = Integer.parseInt(sc.next());
            if (a == 5) {
                fiveCnt++;
            } else if (a == 7) {
                sevenCnt++;
            }
        }
        if (fiveCnt == 2 && sevenCnt == 1) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


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

int main(){
    int x, n;
    cin >> x >> n;
    set<int> s;
    rep(i,n){
        int x; 
        cin >> x;
        s.insert(x);
    }
    if(s.size()== 0){
        cout << x << endl;
        return 0;
    }
    if(s.find(x) == s.end()){
        cout << x << endl;
        return 0;
    }
    int i;
    i =1;
    while (true){
        if(s.find(x-i) == s.end()){
            cout << x-i << endl;
            break;
        }
        else if(s.find(x+i) == s.end()){
            cout << x+i << endl;
            break;
        }
        i++;
    }
}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n;
vector<i64> a, b;
int main() {
  cin >> n;
  read_n(a, n + 1);
  read_n(b, n);

  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    i64 x = min(a[i], b[i]);
    ans += x;
    a[i] -= x;
    b[i] -= x;
    x = min(a[i + 1], b[i]);
    ans += x;
    a[i + 1] -= x;
    b[i] -= x;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};

int main(){
	int N;
	cin>>N;
	cout<<"ABC"<<N;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=3000;
int n,mod;
long long fir[maxn+5],inv[maxn+5],s[maxn+5][maxn+5];
long long ksm(long long x,long long n)
{
	long long ans=1;
	while(n)
	{
		if(n&1) ans=ans*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return ans;
}
long long ksms(long long x,long long n)
{
	long long ans=1;
	while(n)
	{
		if(n&1) ans=ans*x%(mod-1);
		x=x*x%(mod-1);
		n>>=1;
	}
	return ans;
}
void pre()
{
	fir[0]=1;
	for(int i=1;i<=maxn;i++) fir[i]=fir[i-1]*i%mod;
	inv[maxn]=ksm(fir[maxn],mod-2);
	for(int i=maxn-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	s[0][0]=1;
	for(int i=1;i<=n+1;i++)
	for(int j=1;j<=i;j++) s[i][j]=(s[i-1][j]*j+s[i-1][j-1])%mod;
}
long long C(int n,int m)
{
	if(n<m) return 0;
	return fir[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	scanf("%d%d",&n,&mod);
	pre();
	long long ans=0;
	for(int i=0;i<=n;i++)
	{
		int op=(i&1)?-1:1;
		long long mu=ksm(2,n-i),mus=1;
		long long v=ksm(2,ksms(2,n-i));
		for(int j=0;j<=i;j++) ans=(ans+s[i+1][j+1]*v%mod*mus%mod*op%mod*C(n,i)%mod)%mod,mus=mus*mu%mod;
	}
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",ans);
}

Measured memory_bytes: 49972
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

temp1 = 0
temp2 = sum(As)
for i, a in enumerate(As):
    temp1 += As[i]
    temp2 -= As[i]
    r = As[i] * (i+1) - temp1 +\
    temp2 - As[i] * (N-1-i)
    result = min(result, r) if i != 0 else r
print(result)


Measured memory_bytes: 26020
#include <iostream>
#include <vector>
#include <algorithm>

struct data{
    std::string S;
    int in;
    int P;

    data(std::string name, int num, int price)
    {
        S=name;
        in=num;
        P=price;
    }
    bool operator<(const data &another) const
    {
        if(S==another.S){
            return P>another.P;
        }else{
            return S<another.S;
        }
    };
};

int main()
{
    int N;
    std::vector<data> Data;
    int P1;
    std::string S1;
    std::cin >> N;
    for(int i=0; i<N; i++){
        std::cin >>S1;
        std::cin >> P1;
        Data.push_back(data(S1,i,P1));
    }
    std::sort(Data.begin(),Data.end());
    for(int i=0; i<N; i++){
        std::cout << (Data[i].in)+1 << std::endl;
    } 
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000
 
int C[N+1][N+1];
  
int lcs(char *a, char *b){
  int i,j,X,Y;
  
  X = strlen(a);
  Y = strlen(b);
  
  for (i=0;i<X;i++){
    for (j=0;j<Y;j++){
      if (a[i] == b[j])C[i+1][j+1]=C[i][j]+1;
      else C[i+1][j+1]=((C[i][j+1]>C[i+1][j])?C[i][j+1]:C[i+1][j]);
    }
  }
  return C[X][Y];
}

int main(){
  char x[N], y[N];
  int n, i;
  
  scanf("%d", &n);
  for (i=0;i<n;i++){
    scanf("%s%s",x,y);
    printf("%d\n",lcs(x, y));
  }
  return 0;
}



Measured memory_bytes: 5700
#include <vector>
#include <iostream>
#include <limits>
using ll = long long;
constexpr ll INF = 1LL << 60;
using ll = long long;
int main()
{
    int N;
    std::cin >> N;
    std::vector<ll> a(N);
    for (int i = 0; i < N; i++) { std::cin >> a[i]; }
    std::vector<std::vector<ll>> memo(N + 1, std::vector<ll>(N + 1, INF));
    auto dp = [&](auto&& self, const int l, const int r) -> ll {
        if (l > r) { return 0; }
        if (memo[l][r] != INF) { return memo[l][r]; }
        const ll n1 = -self(self, l + 1, r) + a[l];
        const ll n2 = -self(self, l, r - 1) + a[r];
        return memo[l][r] = std::max(n1, n2);
    };
    std::cout << dp(dp, 0, N - 1) << std::endl;
    return 0;
}


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

#define NEW(p,n){p=malloc(n*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}

typedef int*vector;

vector create_vector(int n)
{
  vector v;
  NEW(v,n);
  for(int i=0;i<n;i++){
    v[i]=0;
  }
  return v;
}

int main()
{
  int n;
  scanf("%d",&n);
  vector v=create_vector(n);
  for(int i=0;i<n-1;i++){
    int A;
    scanf("%d",&A);
    v[A-1]+=1;
  }
  for(int i=0;i<n;i++){
    printf("%d\n",v[i]);
  }
  free(v);
  return 0;
}

Measured memory_bytes: 2224
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		try {
			int n = Integer.parseInt(sc.nextLine());
			int ans = n * (n + 1) / 2;

			System.out.println(ans);

		} finally {
			sc.close();
		}
	}
}

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

#define BUF_SIZE 10

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}

#define SET_MAX 1000000
#define INPUT_MAX 999999 // less than or equal
// 6000000**(1/3) = 181.7
// 180*181*182/6 < 181**3/6 < INPUT_MAX < 181*182*183/6
#define NUM_MAX 180
struct pair {
    int min;
    int odd_min;
};

#include <limits.h>
#define min(a,b) ((a) > (b) ? (b) : (a))

int main(void) {
    struct pair ans[SET_MAX] = {0};
    int idx = 0;
    int i;
    int tetra_area[NUM_MAX+1];
    // calc idx:1 ~ 99
    for(i = 1; i <= NUM_MAX; i++) {
        tetra_area[i] = i*(i+1)*(i+2)/6;
    }
    // answer to 1st question
    static int dp[INPUT_MAX+1];
    // answer to 2nd question
    static int odd_dp[INPUT_MAX+1];

    // In case of len = 1
    for(i = 0; i < INPUT_MAX+1; i++) {
        dp[i] = odd_dp[i] = i;
    }
    // calc len limit
    int len;
    for(len = 2; len <= NUM_MAX; len++) {
        int target = tetra_area[len];
        // update dp
        for(i = target; i <= INPUT_MAX; i++) {
            dp[i] = min(dp[i], dp[i-target]+1);
        }
    }
    for(len = 2; len <= NUM_MAX; len++) {
        int target = tetra_area[len];
        if(!(target%2)) continue; //require odd number
        for(i = target; i <= INPUT_MAX; i++) {
            odd_dp[i] = min(odd_dp[i], odd_dp[i-target]+1);
        }
    }
    // query
    while(1) {
        int sum = get_int();
        if(!sum) break;
        ans[idx].min = dp[sum]; ans[idx].odd_min = odd_dp[sum];
        idx++;
    }

    for(i = 0; i < idx; i++) {
        printf("%d %d\n", ans[i].min, ans[i].odd_min);
    }
    return 0;
}


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

using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple

#define N 311111
#define A 1111111
#define BLOCK 555 // ~sqrt(N)

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

const int INF = 1e9 +5;
const int nax = 3005;
const long M = 1000000007;
// double p[305][305][305];
// double ev[305][305][305];
ll dp[nax][nax];
// int visited[nax];
// int in_degree[nax];
// vector<int> edges[nax];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout<<fixed;
	cout<<setprecision(10);
	int t;
	// cin>>t;
	t = 1;
	while(t--){
		int n,k;
		cin>>n;
		int arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		for(int L = n-1;L>=0;L--){
			for(int R = 0; R<=n-1;R++){
				if(L>R){
					dp[L][R]=0;
				}
				else if(L==R){
					dp[L][R] = arr[L];
				}
				else{
					dp[L][R] = max(arr[L] - dp[L+1][R], arr[R]-dp[L][R-1]);
				}
			}
		}
		// string ans = dp[k] ? "First" : "Second";
		cout<< dp[0][n-1] << '\n';
	}
}

Measured memory_bytes: 70656
// 2020-08-24 02:29:28
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  ll n;
  cin >> n;
  REPC(a, 1, 3500) REPC(b, 1, 3500) {
    ll x = n * a * b;
    ll y = 4 * a * b - n * b - n * a;
    if(y != 0 && x % y == 0 && x / y > 0) {
      cout << a << ' ' << b << ' ' << x / y << '\n';
      return;
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

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

int main(){
  int n;
  cin >> n;
  map<string,int> mp;
  
  rep(i,n){
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    mp[s]++;
  }
  ll ans = 0;
  for(auto p : mp){
    int s = p.second;
    ans += (ll)s*(s-1)/2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11136
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-6;
const vi emp;

ll n,A=1,B=1,a,b;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		ll tmpa=(A+a-1)/a*a,tmpb=(B+b-1)/b*b,cb=tmpa/a*b,ca=tmpb/b*a;
		if(cb<B) cb=INF;
		if(ca<A) ca=INF;
		ll sa=tmpa-A+cb-B,sb=tmpb-B+ca-A;
		if(sa<sb){
			A=tmpa;
			B=cb;
		}
		else{
			A=ca;
			B=tmpb;
		}
	}
	cout<<A+B<<endl;
}

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

// long N, ma, mb;
long dp[41][401][401];

int main() {long N, ma, mb;
cin >> N >> ma >> mb;
vector<long> a(N + 1); vector<long> b(N + 1); vector<long> c(N + 1);
erep(i, N) cin >> a.at(i) >> b.at(i) >> c.at(i);
rep(i, N + 1){
  rep(j, 401){
    rep(k, 401){
      dp[i][j][k] = 4001; 
    }
  }
}

dp[0][0][0] = 0;
erep(i, N){
  rep(j, 401){
    rep(k, 401){
      if(j >= a.at(i) && k >= b.at(i)){
        dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a.at(i)][k - b.at(i)] + c.at(i));
      }
      else{
        dp[i][j][k] = dp[i - 1][j][k];
      }
    }
  }
}
long ans = 4001;
erep(i, 10){
  ans = min(ans, dp[N][ma * i][mb * i]);
}
if(ans == 4001) ans = -1;
cout << ans << endl;
  return 0;
 
}



Measured memory_bytes: 51712
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

main :: IO ()
main = do
    [n, r] <- getIntList
    putStrLn . show $ if n < 10 then r + 100 * (10-n) else r


readInt = fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words
getIntList = readIntList <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine


Measured memory_bytes: 380
from collections import deque
N, Q = map(int, input().split())
count = [0 for i in range(N)]
graph = {i:[] for i in range(N)}

for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1]+=[b-1]
  graph[b-1]+=[a-1]

for i in range(Q):
  p, x = map(int, input().split())
  count[p-1] += x

q = deque([0])
log = [True]*N
log[0]=False
while q:
  v = q.popleft()
  ls = graph[v]
  for l in ls:
    if log[l]:
      q.append(l)
      log[l]=False
      count[l] += count[v]
ans = [str(i) for i in count]
print(' '.join(ans))

Measured memory_bytes: 88456
package main

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

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	a := make([]int,n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
	}

	ans1,ans2 := 0,0
	for i := 0; i < n; i++ {
		if ans1 < a[i] {
			ans1,ans2 = a[i], ans1
		} else if ans2 < a[i] {
			ans2 = a[i]
		}
	}

	for i := 0; i < n; i++ {
		if a[i] == ans1 {
			fmt.Println(ans2)
		} else {
			fmt.Println(ans1)
		}
	}
}


Measured memory_bytes: 6400
imp="Impossible"

def ans(a,b)
	puts a.join(" ")
	puts b.length
	puts b.join(" ")
end

n,m=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)
oddc = a.count(&:odd?)
case oddc
when 0
	b = a.dup
	b[0] -= 1
	b << 1
	ans(a,b)
when 1
	if a.length == 1
		if a == [1]
			ans(a,a)
		else
			ans(a,[a[0]-1,1])
		end
		exit
	end
	o,a = a.partition{|x| x.odd? }
	a = o+a
	b = a.dup
	b[0] += 1
	b[-1] -= 1
	ans(a,b)
when 2
	o,a = a.partition{|x| x.odd? }
	a = [o[0],*a,o[1]]
	b = a.dup
	b[0] += 1
	b[-1] -= 1
	b.pop if b[-1] == 0
	ans(a,b)
else
	puts imp
end


Measured memory_bytes: 1788
#include <stdio.h>
#include <string.h>

int main() {
  char a[3], b[3];
  int i, cnt=0;
  
  scanf("%s", a);
  scanf("%s", b);
  
  for (i = 0; i < 3; i++) {
    if(a[i] == b[i]){
    	cnt++;
    }
  }

  printf("%d\n",cnt);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;
 
// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;

int main ()
{
  prep();
  int n, m;
  cin >> n >> m;
  if (n == m){
      cout << "Yes";
  }else{
      cout << "No";
  }
  return 0; 
}


Measured memory_bytes: 256