akhauriyash/Code-Regression huggingface dataset:
// c++include
#include <iostream>
// cinclude
#include <stdio.h>
#include<string.h>
#include<math.h>
//c++標準ライブラリ
#include<vector>
#include<string>
//std使用<-namespace
using namespace std;

// define, typedef
#define rpt(i, n) for(i = 0; i < (n); i++)
typedef long long ll;

// main関数
int main(void) {
	ll n;
	vector<ll> h;
	cin >> n;
	int i;
	ll b;
	rpt(i, n) {
		cin >> b;
		h.push_back(b);
	}
	ll max = 0;
	rpt(i, n) {
		ll count = 0;
		while (true) {
			if (i == n - 1) {
				break;
			}
			else if (h[i] < h[i + 1]) {
				break;
			}
			else {
				count++;
				i++;
			}
		}
		if (max < count) {
			max = count;
		}
	}
	cout << max;
	return 0;
}

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

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

int main()
{   
    int n;
    cin >> n;

    vector<int> ar(n);
    REP(i, n)   cin >> ar[i];
    
    REP(k, n-1) cout << ar[k] << " ";
    cout << ar[n-1] << endl;
    
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        int v = ar[i];
        
        while (j >= 0 && v < ar[j]) {
            ar[j+1] = ar[j];
            j--;
        }

        ar[j+1] = v;

        REP(k, n-1) cout << ar[k] << " ";
        cout << ar[n-1] << endl;
    }
    
}


Measured memory_bytes: 3092
from heapq import*
X,Y,Z=map(int,input().split());N=X+Y+Z;A=[];q1=[];q2=[];L=[0];R=[0]
for _ in[0]*N:A.append([int(e)for e in input().split()])
A.sort(key=lambda a:a[0]-a[1])
for i in range(N):
	L+=[L[i]+A[i][1]];heappush(q1,A[i][1]-A[i][2]);R+=[R[i]+A[-1-i][0]];heappush(q2,A[-1-i][0]-A[-1-i][2])
	if i>=Y:L[i+1]-=heappop(q1)
	if i>=X:R[i+1]-=heappop(q2)
print(max(L[i]+R[N-i] for i in range(Y,N-X+1)))

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

H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)

# 予め組み合わせ計算に必要な階乗と逆元のテーブルを作っておく
factorial = [1] * (H+W)
factorial[0] = 1
factorial[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod

inverse = [1] * (H+W)
# フェルマーの小定理から(x! ** mod-2 % mod == x! ** -1 % mod)
# powに第三引数入れると冪乗のmod付計算を高速にやってくれる
inverse[H+W-1] = pow(factorial[H+W-1], mod-2, mod)
for i in range(H+W-2, 0, -1):
    # 最後から戻っていくこのループならH+W回powするより処理が速い
    inverse[i] = inverse[i+1] * (i+1) % mod

# 組み合わせの数だけ返してくれる関数(自作)
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Measured memory_bytes: 44784
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
int mod =1000000007;
const double PI = acos(-1);

int main(){
    int n;cin>>n;
    string s;cin>>s;
    int r=0,w=0;
    rep(i,n){
        if(s[i]=='R')r++;
        else
        {
             w++;
        }
    }
    int ans =0;
    rep(i,r){
        if(s[i]=='W')ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d=0,e=0;
    cin>>a>>b>>c;
    if(a==5){
        d++;
    }
    else{
        e++;
    }
    if(b==5){
        d++;
    }
    else{
        e++;
    }if(c==5){
        d++;
    }
    else{
        e++;
    }
    if(d==2 && e==1){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define pb push_back
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#ifdef __linux__
#define getchar getchar_unlocked
#endif
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,flag;
LL t,x,y,nx,ny,nt;
int main()
{
	file();
	read(n);
	For(i,1,n)
	{
		read(t),read(x),read(y);
		if(abs(x-nx)+abs(y-ny)>t-nt)flag=1;
		if(((abs(x-nx)+abs(y-ny))&1)!=((t-nt)&1))flag=1;
		t=nt;
		x=nx;
		y=ny;
	}
	printf("%s\n",flag?"No":"Yes");
	return 0;
}


Measured memory_bytes: 256
const N: i64 = 1000000007;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main() {
    let nm:Vec<i64> = read_vec();
    let (n,m)  = (nm[0],nm[1]);
    let ans = if (n-m).abs()  < 2 && m == n{
        2 * (1..n+1).fold(1,|x,y| ( x * y) %N ) *(1..m+1).fold(1,|x,y| ( x * y) %N)
    } else if (n-m).abs()  < 2{
         (1..n+1).fold(1,|x,y| ( x * y) %N ) *(1..m+1).fold(1,|x,y|( x * y) %N )
    } else {
        0
    };
    println!("{}",ans % N );
}

Measured memory_bytes: 4352
def resolve():
    A, B, C, X, Y = list(map(int, input().split()))
    ans = []
    for i in range(0, 100000+1):
        ans.append(i * 2 * C + max(0, X - i) * A + max(0, Y - i) * B)
    print(min(ans))
    return


resolve()

Measured memory_bytes: 12856
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define set_bits(a) __builtin_popcount(a)
#define pb push_back
#define pf push_front
#define mod 1000000007
#define M 998244353
#define fi first
#define se second
#define endl '\n'
#define INF 1e18
#define PI 3.14159265358979323846
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    ll n,i,j,k;
    cin>>n;
    string s;
    cin>>s;
    unordered_map<char,ll>mp;
    for(i=0;i<n;i++)
    {
        mp[s[i]]++;
    }
    ll ans = mp['R']*mp['G']*mp['B'];

    for(i=0;i<n;i++)
    {
        for(j=0;j<i;j++)
        {
            k =  i + (i-j);
            if(k<n)
            {
                if(s[i]==s[j] || s[j]==s[k] || s[i]==s[k])
                {
                    continue;
                }
                ans--;
            }
        }
    }

    cout<<ans<<endl;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

void insert(int);
void preorder(Node);
void inorder(Node);
void treeDelete(Node);
Node treeMinimum(Node);
Node getSuccessor(Node);
Node treeSearch(Node, int);

#define NIL NULL

Node root;

Node treeMinimum(Node x){
while(x->left != NIL) x = x->left;
return x;
}

Node treeSearch(Node u, int k){
    while (u != NIL && k != u->key){
        if(k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void treeDelete(Node z){
    Node x;
    Node y;
    if(z->left == NIL || z->right == NIL) y = z;
    else y = getSuccessor(z);
    if(y->left != NIL) x = y->left;
    else x = y->right;
    if(x != NIL) x->parent = y->parent;
    if(y->parent == NIL) root = x;
    else if(y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
    if(y!=z)z->key = y->key;
}

Node getSuccessor(Node x){
    Node y;
    if(x->right != NIL) return treeMinimum(x->right);
    y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
    }

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

     while (x != NIL){
         y = x;
         if (z->key < x->key)
             x = x->left;
         else 
             x = x->right;
     }
     z->parent = y;
    if (y == NIL)
        root = z;
    else if (z->key < y->key)
        y->left = z;
    else 
        y->right = z;

}

void inorder(Node u){
if (u == NIL) return;
inorder(u->left);
printf(" %d", u->key);
inorder(u->right);
}

void preorder(Node u){
    if(u == NIL) return;
    printf(" %d", u->key);
preorder(u->left);
preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
      scanf("%s", com);
      if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
      }
      if(com[0] == 'i'){
          scanf("%d", &x);
      insert(x);
      }
      else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
}
 else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
}
  return 0;
}



Measured memory_bytes: 20608
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<int, int>;
vector<ii> dirs = {
    {1, 0}, {0, 1}, {-1, 0}, {0, -1},  // 4方向
    {1, 1}, {-1, 1}, {-1, -1}, {1, -1},  // 斜め
    {0, 0},  // 自身
};
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <class T, class S> vector<T> make_vec(size_t n, S x) { return vector<T>(n, x); }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...)); }

// debug
template <class T> ostream& operator<<(ostream& s, vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream& s, vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream& s, pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
    #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
    #define dump(...)
    #define endl "\n"
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }

struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int MOD = 1000000007;
// *************** TEMPLATE END *************** 

signed main() {
    string s; cin >> s;
    int n = s.size();
    int st = 0;
    int acc = 0, prev = -1;
    vector<int> ans(n);
    REP (i, n + 1) {
        dump(i, st, acc);
        if (i == n || st == 1 && s[i] == 'R') {
            ans[prev] += (acc + 1) / 2;
            ans[prev - 1] += acc / 2;
            acc = 1, st = 0;
        } else if (st == 0 && s[i] == 'R') {
            acc++;
        } else if (st == 0 && s[i] == 'L') {
            ans[i - 1] += (acc + 1) / 2;
            ans[i] += acc / 2;
            acc = 1, st = 1;
            prev = i;
        } else if (st == 1 && s[i] == 'L') {
            acc++;
        } else assert(0);
    }
    for (int x : ans) cout << x << ' ';
    cout << endl;
}


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

using namespace std;

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

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===




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

	int N;
	cin >> N;
	string S;
	cin >> S;

	int ans = 0;

	char now = S[0];

	for (int i = 0; i < N; ++i) {
		if (S[i] != now) {
			++ans;
			now = S[i];
		}
	}

	++ans;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 20000000
#define mod 1000000007
#define INF2 1000000000000000000
typedef pair<int, int> P;

int V;
vector<int> G[100010];
int d[100010];
int pi[100010];
void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d + V + 1, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i = 0; i < G[v].size(); i++){
            int to = G[v][i];
            if (d[to] > d[v] + 1) {
                d[to] = d[v] + 1;
                pi[to] = v; 
                //cout << to << " " <<v << endl;
                que.push(P(d[to], to));
            }
        }
    }
}



int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    V = n;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dijkstra(0);
    cout << "Yes" << endl;
    rep(i, n - 1) {
        cout << pi[i + 1] + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 11252
def main(argv)
  (x, a, b) = STDIN.gets.chomp.split(' ').map(&:to_i)
  if b <= a then
    STDOUT.puts 'delicious'
  elsif b <= x + a then
    STDOUT.puts 'safe'
  else
    STDOUT.puts 'dangerous'
  end
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1788
L, R = map(int, input().split())

MIN = 2018
if R-L > 4039:
    MIN = 0


MOD = 2019
L = L%MOD
R = R%MOD
if L > R:
    L, R = R, L
elif L == R:
    MIN = 0


for i in range(L, R):
    for j in range(i+1, R+1):
        buf = (i*j) % MOD
        #print(i, j)
        MIN = min(buf, MIN)

print(MIN)

Measured memory_bytes: 3064
#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;
const int INF = 1e9;

int main()
{
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    sort(x.begin(), x.end());

    ll ans = INF; int s = x[0], t = x[n-1];

    for (int i = s; i <= t; i++) {
        ll num = 0;
        rep(j,n) {
            ll a = pow(x[j]-i, 2);
            num += a;
        }
        ans = min(ans, num);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
pl=list(map(int,input().split()))
ql=list(map(int,input().split()))

import itertools
seq=[i for i in range(1,n+1)]
#print(list(itertools.permutations(seq)))
li=list(itertools.permutations(seq))
p=tuple(pl)
q=tuple(ql)

a=li.index(p)+1
b=li.index(q)+1

print(abs(a-b))

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

using namespace std;

queue<int> q;

vector<int> trail[2*100000];
int n, m;

int answers[2*100000];

int main(){
  cin >> n >> m;
  cin.ignore();

  for(int i = 0; i < 200000; i++){
    answers[i] = INT_MAX;
  }

  int tmpa, tmpb;
  for(int i = 0; i < m; i++){
    cin >> tmpa >> tmpb;
    cin.ignore();
    --tmpa;
    --tmpb;
    trail[tmpa].push_back(tmpb);
    trail[tmpb].push_back(tmpa);
  }

  q.push(0);
  int tmp;
  int max = INT_MAX;
  while(!q.empty()){
    if(q.size() == n) break;
    tmp = q.front();
    q.pop();
    if(trail[tmp].empty()) continue;

    int ttmp;
    for(int i = 0; i < trail[tmp].size(); i++){
      ttmp = trail[tmp][i];
      if(answers[ttmp] != INT_MAX) continue; // 訪問済み
      answers[ttmp] = tmp;
      q.push(ttmp);
    }
  }

  cout << "Yes" << endl;

  for(int i = 1; i < n; i++){
    cout << answers[i] + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 13140
from collections import defaultdict

f = defaultdict(list)
d = {}


s = list(input())
t = list(input())

len_s = len(s)

for i in range(len_s):
    f[s[i]].append(i)

next_char = [[0] * len_s for _ in range(len(f))]

j = 0
for k, v in f.items():
    d[k] = j
    l = 0
    for i in range(len_s):
        if v[l] == i:
            l += 1
            if l == len(v):
                l = 0
        next_char[j][i] = v[l]
    j += 1

m = 0

for i in range(len(t)):
    x = t[i]
    if i == 0 and t[i] == s[i]:
        continue 
    if d.get(x) == None:
        m = -2
        break
    else:
        j = d[x]
        r = m % len_s
        n = next_char[j][r]
        if r >= n:
            m += len_s - (r-n)
        else:
            m += n - r

print(m+1)



Measured memory_bytes: 107964
#include<stdio.h>
int main(){
  int i,j,count,ans,lenght_t,lenght_s;
  char s[1000],t[1000];

  for(i=0;s[i-1]!='\n';i++){
    scanf("%c",&s[i]);
  }
  lenght_s = i-1;
  for(i=0;t[i-1]!='\n';i++){
    scanf("%c",&t[i]);
  }
  lenght_t = i-1;

  ans = lenght_t;

  for(i=0;i<=lenght_s - lenght_t;i++){
    count = 0;
    for(j=0;j<lenght_t;j++){
      if( t[j] != s[i+j] ){
        count++;
      }
    }
    if(count < ans) ans = count;
  }

  if(count < ans){
    printf("%d\n",count);
  }else{
    printf("%d\n",ans);
  }

  return 0;
}


Measured memory_bytes: 2044
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};

template <typename T>
bool chmax(T &a, const T& b) {if (a < b) {a = b;return true;}return false;}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    vector<P> a(n);
    vector<vector<int>> g(n,vector<int>(0));
    int x,y;
    rep(i,n-1){
        cin>>x>>y;
        a[i]=P(x-1,y-1);
        g[x-1].emplace_back(y-1);
        g[y-1].emplace_back(x-1);
    }
    int num_col=0;
    int par=-1;
    rep(i,n){
        x=g[i].size();
        if(chmax(num_col,x)) par=i;
    }
    cout<<num_col<<endl;
    map<P,int> col;
    int cnt=0;
    queue<P> que;
    que.emplace(par,0);
    while(cnt<n-1){
        tie(x,y)=que.front();
        que.pop();
        int now=1;
        for(auto z:g[x]){
            if(col[P(x,z)] || col[P(z,x)]) continue;
            if(now==y) now ++;
            col[P(x,z)]=now;
            cnt ++;
            que.emplace(z,now);
            now ++;
        }
    }
    rep(i,n-1){
        tie(x,y)=a[i];
        cout<<max(col[P(x,y)],col[P(y,x)])<<endl;
    }
}/*
./problem.exe
*/


Measured memory_bytes: 22108
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n,m;
  cin>>n>>m;
  cout << (n - 1) * (m - 1) << endl;

  return 0;
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A: AtCoder Beginner Contest 999
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  char s[8];
  scanf("%s", s);

  for (char *cpt = s; *cpt; cpt++)
    putchar((*cpt == '1') ? '9' : '1');
  putchar('\n');

  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Lesson8C 与えられた英文に含まれる、各アルファベットの数を数えるプログラム
 * なお、小文字と大文字は区別しない
 *
 * @author Internship
 *
 */
public class Main{

	/**
	 * プログラムのエントリポイント
	 *
	 * @param args
	 */
	public static void main(String[] args) {

		//a ~ｚのパターン
		char[] chaAZ = {'a','b','c','d','e','f',
				'g','h','i','j','k','l','m','n',
				'o','p','q','r','s','t',
				'u','v','w','x','y','z'};

		//a?zのパターンが各何回あるかカウントする場所
		int[] intAZ = new int[26];

		//各行読み込む
		try {
			BufferedReader insBR = new BufferedReader(new InputStreamReader(System.in));

			String strLine = "a";
			while((strLine = insBR.readLine())!=null){

			if(strLine.equals("")) {
				break;
			}

			//大文字は小文字にしておく
			strLine = strLine.toLowerCase();

			//char型に分解
			char[] chaAryLine = strLine.toCharArray();

			//各a?z何回あるかカウント
			for(int i = 0; i < chaAryLine.length; i++) {
				for(int j = 0; j < intAZ.length; j++) {
					if(chaAryLine[i] == chaAZ[j]) {
						intAZ[j]++;
					}
				}
			}
			}

			//出力
			for(int i = 0; i < intAZ.length; i++) {
				System.out.println(chaAZ[i] + " : " + intAZ[i]);
			}

		} catch (IOException e) {
			System.out.println(e);
		}

	}
}

Measured memory_bytes: 17844
#include<stdio.h>
int poss,h,w;
void solve(int x,int y);
char ban[100000][10];
int went[100000][10];

void solve(int x,int y){
	went[x][y]++;
	if(x==h-1 && y==w-1){
		poss=1;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(ban[i][j]=='#' && went[i][j]==0){
					poss=0;
					break;
				}
			}
			if(poss==0){
				break;
			}
		}
	}
	if(ban[x+1][y]=='#' && poss!=1){
		solve(x+1,y);
	}
	if(ban[x][y+1]=='#' && poss!=1){
		solve(x,y+1);
	}
	went[x][y]--;
	return;
}

int main(void){
	int i;
	
	scanf("%d %d",&h,&w);
	for(i=0;i<h;i++){
		scanf("%s",ban[i]);
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			went[i][j]=0;
		}
	}
	
	poss=0;
	solve(0,0);
	if(poss==1){
		printf("Possible\n");
	}else{
		printf("Impossible\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
    int k,n;
    cin >> n >> k;
    long long a[n];
    long long ans = 0;
    long long p,m;
    p = m = 0;
    for(int i = 0;i<k;i++){
        cin >> a[i];
        if(a[i]>=0){
            ans+=a[i];
            p+=a[i];
        }
        else m+=abs(a[i]);
    }
    long long sac = min(p,m);
    for(int i = k;i<n;i++){
        cin >> a[i];
        if(a[i-k]>=0)p-=a[i-k];
        else m-=abs(a[i-k]);
        if(a[i]>=0){
            ans+=a[i];
            p+=a[i];
        }
        else m+=abs(a[i]);
        sac = min(sac,min(p,m));        
    }
    cout << ans-sac << endl;
}

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

int main(){
	int H, W; cin >> H >> W;
	
	int ans;
	if(H % 3 == 0 || W % 3 == 0){
		ans = 0;
	}
	else{
		int S_max, S_min = 0;
		//縦三分割
		int h = H / 3;
		S_max = (h + 1) * W;
		S_min = (H - h - 1) / 2 * W;
		ans = S_max - S_min;

		S_min = (H - h - 1) * (W / 2);
		ans = min(ans, S_max - S_min);

		S_min = h * W;
		S_max = (H - h) * ((W + 1) / 2);
		ans = min(ans, S_max - S_min);

		//横三分割
		int w = W / 3;
		S_max = (w + 1) * H;
		S_min = (W - w - 1) / 2 * H;
		ans = min(ans, S_max - S_min);

		S_min = (W - w - 1) * (H / 2);
		ans = min(ans, S_max - S_min);

		S_min = w * H;
		S_max = (W - w) * ((H + 1) / 2);
		ans = min(ans, S_max - S_min);
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 256
def g l,x;l[0]?($h[l.sort]||=l.map{(f,w,s),*a=l.rotate!;s<x-w ?[0,1e9]:(a,b=g(a,x-w);[[f]+a,b+x])}.min_by{|i,j|j}):[[],0]end
while(n=gets.to_i)>x=0
l=(1..n).map{f,w,s=gets.split;x+=w=w.to_i;[f,w,s.to_i]}
$h={}
puts g(l,x)[0]end

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

#define endl '\n'
#define ll long long int
#define let(x, a) __typeof(a) x(a)
#define all(a) (a).begin(), (a).end()
#define present(c, x) ((c).find(x) != (c).end())
#define tr(v, it) for (let(it, v.begin()); it != v.end(); it++)
#define rtr(v, it) for (let(it, v.rbegin()); it != v.rend(); it++)

#define trace1(x)					cerr << #x << ": " << x << endl;
#define trace2(x, y)				cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)				cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)		cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f)	cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	ll n,d,x,y,ans=0;
	cin>>n>>d;
	while(n--) {
		cin>>x>>y;
		if(x*x + y*y <= d*d) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  long long sum = 0;
  for (int i = 1; i <= N; i++) {
    if (i % 3 != 0 && i % 5 != 0) {
      sum += i;
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 3632
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

D, G = LI()
PC = []
for i in range(D):
    PC.append([(i+1)*100] + LI())

PC = [tuple(i) for i in PC]

results = []
# 完答しない場合もある。
result = 0
count = 0
for i in range(PC[-1][1]):
    result += PC[-1][0]
    count += 1
    if result >= G:
        results.append(count)

for i in range(1, D+1):
    # i種類の組み合わせを選ぶ
    combis = list(itertools.combinations(PC, i))
    #  print('i, combis', i, combis)
    for combi in combis:
        # iは完答する種類数
        result = 0
        result += sum([c[0] * c[1] + c[2] for c in combi])
        count = sum([c[1] for c in combi])
        if result >= G:
            results.append(count)
            continue
        rest = [_ for _ in PC if _ not in combi]
        for r in rest[::-1]:
            for ridx in range(r[1]):
                result += r[0]
                count += 1
                if result >= G:
                    results.append(count)
print(min(results))


Measured memory_bytes: 70360
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pf(n) printf("%lld\n",n)
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);


int main() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	bool zero = false;
	rep(i, n) {
		cin >> a[i];
		if (a[i] == 0) zero = true;
	}
	if (zero) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = 1;
	ll n18 = 1;
	rep(i, 18) n18 *= 10;

	rep(i, n) {
		//pf(a[i]);
		//pf(ans);
		//printf("%lf\n", 1e+18 / a[i]);
		if (a[i] <= n18 / ans) {
			ans *= a[i];
		}
		else {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4024
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

VI g[1010];
string s[1010];

int dfs(int m, int d) {
	REP(i, g[m].size()) {
		REP(j, d) cout << ".";
		cout << s[g[m][i]] << endl;
		dfs(g[m][i], d+1);
	}
}

signed main(void)
{
	int n;
	cin >> n;
	REP(i, n) {
		int a;
		cin >> a;
		g[a].PB(i+1);
		cin >> s[i+1];
	}
	cout << s[1] << endl;
	dfs(1, 1);

	return 0;
}

Measured memory_bytes: 3420
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int N,M;
int cum[100010];

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

  cin >> N >> M;
  REP(i,M) {
    int L,R;
    cin >> L >> R;
    cum[L-1]++;
    cum[R]--;
  }
  REP(i,N) cum[i+1] += cum[i];
  int ans = 0;
  REP(i,N) ans += (cum[i] >= M);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
# coding: utf-8
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
list = make_divisors(N)

if len(list)%2 == 0:
    a,b = list[-2],list[-1]
    print(a+b-2)
else:
    a = list[-1]
    print(2*a-2)

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
const ll INF = (1ll << 60);

int main() {
  ll H, W;
  cin >> H >> W;

  vvi G(H, vi(W));
  for (ll i = 0; i < H; i++) {
    string s;
    cin >> s;
    for (ll j = 0; j < W; j++) {
      if (s[j] == '#') {
        G[i][j] = 1;
      }
    }
  }

  vvi A(H - 1, vi(W - 1));
  for (ll i = 0; i < H - 1; i++) {
    for (ll j = 0; j < W - 1; j++) {
      if ((G[i][j] + G[i][j + 1] + G[i + 1][j] + G[i + 1][j + 1]) % 2) {
        A[i][j] = 1;
      }
    }
  }

  vvi B(H - 1, vi(W - 1));
  for (ll i = 0; i < H - 1; i++) {
    for (ll j = 0; j < W - 1; j++) {
      if (A[i][j]) {
        B[i][j] = 0;
      } else {
        if (i == 0)
          B[i][j] = 1;
        else
          B[i][j] = B[i - 1][j] + 1;
      }
    }
  }

  ll ans = 0;

  for (ll i = 0; i < H - 1; i++) {
    stack<pair<ll, ll>> s;
    for (ll j = 0; j < W - 1; j++) {
      if (s.size() == 0 && B[i][j] > 0) {
        s.push({j, B[i][j]});
      } else if (s.size() && B[i][j] > s.top().second) {
        s.push({j, B[i][j]});
      } else if (s.size() && B[i][j] < s.top().second) {
        ll l = -1;
        while (s.size() && B[i][j] < s.top().second) {
          ans = max(ans, (s.top().second + 1) * (j - s.top().first + 1));
          l = s.top().first;
          s.pop();
        }
        if (B[i][j])
          s.push({l, B[i][j]});
      }
    }

    while (s.size()) {
      ans = max(ans, (s.top().second + 1) * (W - s.top().first));
      s.pop();
    }
  }

  ans = max(ans, H);
  ans = max(ans, W);

  cout << ans << endl;
}

Measured memory_bytes: 96128
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<set>
#include<tuple>

using namespace std;
typedef long long ll;

const ll MAX = 1000+1;
struct point
{
    ll p, i, j, k;
    point(ll p,ll i,ll j, ll k):p(p),i(i),j(j),k(k){}

    bool operator< (const point &rhs)const
    {
        return p < rhs.p;
    }
        
};



int main(){
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    for (ll i = 0; i < x; i++)
    {
        cin >> a[i];
    }
    for (ll i = 0; i < y; i++)
    {
        cin >> b[i];
    }
    for (ll i = 0; i < z; i++)
    {
        cin >> c[i];
    }
    sort(a.begin(), a.end(), greater<ll>());
    sort(b.begin(), b.end(), greater<ll>());
    sort(c.begin(), c.end(), greater<ll>());
    priority_queue<point> pq;
    set<tuple<ll,ll,ll>> s;
    pq.push(point(a[0] + b[0] + c[0], 0, 0, 0));
    s.insert(make_tuple(0, 0, 0));
    for (ll l = 0; l < k; l++)
    {
        point p = pq.top();
        ll i = p.i;
        ll j = p.j;
        ll k = p.k;
        cout << p.p << endl;
        pq.pop();
        if(i+1<x &&s.find(make_tuple(i+1,j,k))==s.end())
        {
            pq.push(point(a[p.i + 1] + b[p.j] + c[p.k], p.i + 1, p.j, p.k));
            s.insert(make_tuple(i+1,j,k));
        }
        if(j+1<y&&s.find(make_tuple(i,j+1,k))==s.end())
        {
            pq.push(point(a[p.i] + b[p.j + 1] + c[p.k], p.i, p.j + 1, p.k));
            s.insert(make_tuple(i,j+1,k));
        }
        if(k+1<z&&s.find(make_tuple(i,j,k+1))==s.end())
        {
            pq.push(point(a[p.i] + b[p.j] + c[p.k + 1], p.i, p.j, p.k + 1));
            s.insert(make_tuple(i,j,k+1));
        }
    }
    return 0;
}

Measured memory_bytes: 896
import sys
n=input()
n=int(n)
a=input().split()
ans=1
v=[]
for m in a:
    m=int(m)
    if(m==0):
        print(0)
        sys.exit()
    else:
        v.append(m)
for m in v:
    if(ans>1e18):
        print(-1)
        sys.exit()
    else:
        ans*=m
if(ans>1e18):
    print(-1)
else :
    print(ans)


Measured memory_bytes: 21476
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;


    void solve()
    {
        var N = cin.nextlong;
        if (N < 10)
        {
            WriteLine(N);
        }
        else
        {
            long ans = 0;
            var S = N.ToString();
            for (int i = 0; i < S.Length; i++)
            {
                ans += S[i] - '0';
            }

            for (int i = 0; i < S.Length; i++)
            {
                long tmp = 0;
                //i番目で1減らす
                for (int j = 0; j < S.Length; j++)
                {
                    if (j < i)
                    {
                        tmp += S[j] - '0';
                    }
                    else if (j == i)
                    {
                        tmp += S[j] - '0';
                        tmp--;
                    }
                    else
                    {
                        tmp += 9;
                    }
                }
                ans = Math.Max(tmp, ans);
            }
            WriteLine(ans);
        }
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int N=2005,inf=0x3f3f3f3f;
int u[N],v[N],h[N],ne[N<<1],to[N<<1],dep[N];
int n,tot,ans,js,K;
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x,int las) {
	for(RI i=h[x];i;i=ne[i])
		if(to[i]!=las) dep[to[i]]=dep[x]+1,dfs(to[i],x);
}
int main()
{
	n=read(),K=read();
	for(RI i=1;i<n;++i)
		u[i]=read(),v[i]=read(),add(u[i],v[i]),add(v[i],u[i]);
	ans=inf;
	if(K&1) {
		for(RI i=1;i<n;++i) {
			dep[u[i]]=dep[v[i]]=0,dfs(u[i],v[i]),dfs(v[i],u[i]),js=0;
			for(RI j=1;j<=n;++j) if(dep[j]>K/2) ++js;
			ans=min(ans,js);
		}
	}
	else {
		for(RI i=1;i<=n;++i) {
			dep[i]=0,dfs(i,0),js=0;
			for(RI j=1;j<=n;++j) if(dep[j]>K/2) ++js;
			ans=min(ans,js);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e9+7;
int a[200005];
int main()
{
    //freopen("input.txt","r",stdin);
    int n,k;cin>>k>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int sum=-1;
    for(int i=1;i<n;i++)
    {
        sum=max(abs(a[i]-a[i-1]),sum);
    }
    sum=max(k-abs(a[0]-a[n-1]),sum);
    cout<<k-sum<<endl;
    return 0;
}


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

using namespace std;
typedef pair<int, int> PP;
int N;
int P[100];

PP dp[100][50000];

PP max(PP a, PP b){
	if(a.first == b.first){
		if(a.second > b.second){
			return b;
		}else{
			return a;
		}
	}else if(a.first >= b.first){
		return a;
	}else{
		return b;
	}
}

PP recur(int idx, int kozeni){
	if(idx == N){
		return make_pair(0, 0);
	}
	if(dp[idx][kozeni].first != -1){
		return dp[idx][kozeni];
	}
	PP ans = recur(idx + 1, kozeni);
	int nk = (1000 - P[idx] % 1000) % 1000;
	if(nk >= 500){
		PP ans2 = recur(idx + 1, kozeni + nk - 500);
		ans = max(ans, make_pair(ans2.first + 1, ans2.second + P[idx]));

	}else{
		PP ans2 = recur(idx + 1, kozeni + nk);
		ans = max(ans, make_pair(ans2.first, ans2.second + P[idx]));
		if(kozeni + nk >= 500){
			ans2 = recur(idx + 1, kozeni + nk - 500);
			ans = max(ans, make_pair(ans2.first + 1, ans2.second + P[idx]));
		}
	}
	return dp[idx][kozeni] = ans;
}

int main(){
	while(1){
		scanf("%d", &N);
		if(!N) break;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < 50000; j++){
				dp[i][j] = make_pair(-1, -1);
			}
		}

		for(int i = 0; i < N; i++){
			scanf("%d", &P[i]);
		}
		PP ans = recur(0, 0);
		printf("%d %d\n", ans.first, ans.second);
	}
}

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




using namespace std;

int main() {
	long long int N, A, B;
	cin >> N >> A >> B;
	string S;
	cin >> S;
	long long int AA = 0, BB = 0;
	for( size_t i = 0; i < S.size(); i++ ) {
		if( S[i] == 'a' ) {
			AA++;
			if( AA + BB <= A + B ) {
				cout << "Yes" << endl;
			} else {
				AA--;
				cout << "No" << endl;
			}
		} else if( S[i] == 'b' ) {
			BB++;
			if( AA + BB <= A + B&&BB <= B ) {
				cout << "Yes" << endl;
			} else {
				BB--;
				cout << "No" << endl;
			}
		} else {
			cout << "No" << endl;
		}
	}

}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-
import sys

(A,B,C) = map(int,input().split(" "))

history = {}
result = 0

while A%2 == 0 and B%2 == 0 and C%2 == 0:
    key = " ".join(map(str,[A,B,C]))
    if key in history:
        result=-1
        break
    history[key] = 1
    a = (B+C)//2
    b = (A+C)//2
    c = (A+B)//2
    A = a
    B = b
    C = c

    result = result +1

print(result)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define double long double
#define pii pair<int, int>
#define FOR(i, a, b) for(int i = a; i < (int)(b); ++i)
#define all(x) x.begin(), x.end()
#define deb(x) cout << (#x) << " is " << (x) << endl;
const int mod = 1000 * 1000 * 1000 + 7;
using namespace std;

inline int add(int a, int b){
	a += b;
	// if(a >= mod)
    //     a -= mod;
    a %= mod;
	return a;
}
 
inline int sub(int a, int b){
	a -= b;
	if(a < 0)
        a += mod;
	return a;
}

int32_t main() {
    int n, k;
    cin >> n >> k;
    int a[n + 1];
    FOR(i, 1, n + 1) {
        cin >> a[i];
    }
    int d[n + 1][k + 1];
    int p[n + 1][k + 1];
    memset(d, 0, sizeof(int) * (n + 1) * (k + 1));
    memset(p, 0, sizeof(int) * (n + 1) * (k + 1));
    FOR(i, 0, a[1] + 1) {
        d[1][i] = 1;
    }
    p[1][0] = d[1][0];
    FOR(i, 1, k + 1) {
        p[1][i] = add(p[1][i - 1], d[1][i]);
    }
    FOR(i, 2, n + 1) {
        FOR(j, 0, k + 1) {
            if (j - a[i] > 0) {
                d[i][j] = sub(p[i - 1][j], p[i - 1][j - a[i] - 1]);
            }
            else {
                d[i][j] = p[i - 1][j];
            }

            if (j > 0)
                p[i][j] = add(p[i][j - 1], d[i][j]);
            else 
                p[i][j] = d[i][j];
                
        }
    }
    cout << d[n][k];
    return 0;
}

Measured memory_bytes: 161336
// In the name of God

#include <bits/stdc++.h>

using namespace std;

map<int,int> mp;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		mp[x]++;
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; i++) {
		int x;
		cin >> x;
		if(mp[x] == 0) {
			cout << "NO";
			exit(0);
		}
		mp[x]--;
	}
	cout << "YES";

	return 0;
}


Measured memory_bytes: 9600
#include<cstdio>
#define maxn 100005
int n,m,fa[maxn],dist[maxn];
int findset(int x)
{
	if(fa[x]==x) return x;
	int f=fa[x];
	fa[x]=findset(fa[x]);
	dist[x]+=dist[f];
	return fa[x];
}
int main()
{
	bool f=false;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(f) continue;
		int r1=findset(u),r2=findset(v);
		if(r1!=r2)
		{
			fa[r2]=r1;
			dist[r2]=dist[r1]+w-dist[v]+dist[u];
		}
		else if(dist[v]-dist[u]!=w) f=true;
	}
	printf("%s\n",f?"No":"Yes");
}

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

using namespace std;


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s)
{
    return '"' + s + '"';
}

string to_string(const char* s)
{
    return to_string((string) s);
}

string to_string(bool b)
{
    return (b ? "true" : "false");
}

string to_string(vector<bool> v)
{
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v)
{
    string res = "";
    for (size_t i = 0; i < N; i++)
    {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v)
{
    bool first = true;
    string res = "{";
    for (const auto &x : v)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p)
{
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out()
{
    cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const double eps = 1e-10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    int cur = 7;
    int ans = -1;
    for (int i = 1; i <= k; i++)
    {
        if (cur % k == 0)
        {
            ans = i;
            break;
        }
        cur *= 10;
        cur += 7;
        if (cur >= k)
        {
            cur %= k;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3660
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
long long dp[N];

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

	int n, W;
	cin >> n >> W;
	for (int i = 0; i < n; i++) {
		int w, v;
		cin >> w >> v;
		for (int j = W; j >= w; j--)
			dp[j] = max(dp[j], dp[j - w] + v);
	}
	cout << *max_element(dp, dp + N) << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>
#include <numeric>
#include <tuple>




typedef long long ll;


using namespace std;

typedef pair<int, int> P;
#define FOR(i,a,b) for(int i=(int)(a) ; i < (int) (b) ; ++i )
#define rep(i,n) FOR(i,0,n)
#define sz(x) int(x.size())


template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;

int gcd(int x,int y){
    if (y==0) return x;
    else return gcd(y,x%y);
}

int main(){
    int a,b;
  	cin>>a>>b;
  	a*b%2==0? cout<<"No":cout<<"Yes"; 
    
    return 0;
}



Measured memory_bytes: 256