akhauriyash/Code-Regression huggingface dataset:
N = input()
N_list = list(N)
N = int(N)
K = len(N_list)

ans = int(N_list[0])+(K-1)*9
ans_list = [N_list[0]] + ['9' for _ in range(K-1)]
ans_cand = int(''.join(ans_list))
if N < ans_cand:
    print(ans - 1)
else:
    print(ans)

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n;
vector<lint> a, sum;
vector<int> memo;

int solve(int i){
    if(memo[i] >= 0){
        return memo[i];
    }
    int j = upper_bound(ALL(a), sum[i] << 1) - a.begin();
    --j;
    if(i >= j){
        return memo[i] = 0;
    }
    return memo[i] = solve(j);
}

int main(){
    cin >> n;
    a.resize(n);
    memo.resize(n);
    fill(ALL(memo), -1);
    memo[n - 1] = 1;
    rep(i, n){
        cin >> a[i];
    }
    SORT(a);
    sum.resize(n);
    sum[0] = a[0];
    REP(i, 1, n){
        sum[i] = sum[i - 1] + a[i];
    }
    int ans = 0;
    rep(i, n){
        ans += solve(i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2176
import java.util.*;
import java.lang.Math;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
   	int n = sc.nextInt();
    String s = sc.next();
    int stack;
    char chs[] = new char[s.length()];
    
    for(int i = 0; i < s.length();i++){
    	stack = (int)s.charAt(i) + n;
      	if(stack > 90) stack -=26;
      	chs[i] = (char)stack;
    }
    s = new String(chs);
    
    System.out.println(s);

  }
}


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


int main() {
  long int N,K;
  cin >> N >> K;
  
  long int count = 1;
  long int a = 1;
  for(long int i=0;i<1000000000000;i++){
    a = a* K;
    if(N >= a) count++;
    else break;
  }
  cout << count << endl;
}


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

using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    long long d, v;
    cin >> n >> d >> v;
    vector<pair<long long, long long>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    deque<pair<long long, long long>> q;
    long long tot = 0;
    long long ans = 0;
    for (auto pr: a) {
        while (q.size() > 0 && pr.first > q.front().first) {
            tot -= q.front().second;
            q.pop_front();
        }
        if (tot < pr.second) {
            auto r = pr.second - tot;
            auto cnt = r/v + (r%v > 0 ? 1 : 0);
            auto cur = cnt*v;
            tot += cur;
            ans += cnt;
            q.push_back({pr.first + 2*d, cur});
        }
    }
    cout << ans << endl;
}



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

int main(){
    string S;
    cin >> S;
    for(int i=0;i<S.size();i++){
        if(i%2==1){
            if(S[i]=='R'){
                cout << "No" <<endl;
                return 0;
            }
        }
        else{
            if(S[i]=='L'){
                cout <<"No" <<endl;
                return 0;
            }
        }
    }
    cout << "Yes" <<endl;
    return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
ls = []
ans = 0
for i in range(h):
    ls.append(input())
for i in range(w):
    for j in range(h):
        if ls[j][i] == '.':
            pass
        elif j == h-1 and i == w-1:
            if ls[j-1][i] == '#' or ls[j][i-1] == '#':
                pass
            else:
                ans = 1
                break
        elif j == h-1 and i == 0:
            if ls[j-1][i] == '#' or ls[j][i+1] == '#':
                pass
            else:
                ans = 1
                break
        elif j == 0 and i == w-1:
            if ls[j+1][i] == '#' or ls[j][i-1] == '#':
                pass
            else:
                ans = 1
                break
        elif j == 0 and i == 0:
            if ls[j-1][i] == '#' or ls[j][i-1] == '#':
                pass
            else:
                ans = 1
                break
        elif j == 0:
            if ls[j+1][i] == '#' or ls[j][i-1] == '#' or ls[j][i+1] == '#':
                pass
            else:
                ans = 1
                break
        elif i == 0:
            if ls[j-1][i] == '#' or ls[j+1][i] == '#' or ls[j][i+1] == '#':
                pass
            else:
                ans = 1
                break
        elif j == h-1:
            if ls[j-1][i] == '#' or ls[j][i-1] == '#' or ls[j][i+1] == '#':
                pass
            else:
                ans = 1
                break
        elif i == w-1:
            if ls[j-1][i] == '#' or ls[j+1][i] == '#' or ls[j][i-1] == '#':
                pass
            else:
                ans = 1
                break
        
        
        else:
            if ls[j-1][i] == '#' or ls[j+1][i] == '#' or ls[j][i-1] == '#' or ls[j][i+1] == '#':
                pass
            else:
                ans = 1
                break
    if ans == 1:
        break
if ans == 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3192
#[allow(unused_imports)]
use std::collections::HashSet;

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()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<usize>();
    let w = read_vec::<i32>();

    let answer = solve(n, &w);
    println!("{}", answer);
}

fn solve(n: usize, w:&[i32]) -> i32 {
    let mut sum:Vec<i32> = vec![0; n];
    sum[0] = w[0];
    for i in 1..n {
        sum[i] = sum[i-1] + w[i];
    }
    
    let boundary = binary_search(n, &sum);
    let v1 = get_diff(n, boundary, &sum).abs();
    if v1 == 0 || boundary == n -2 {
        return v1;
    }
        
    let v2 = get_diff(n, boundary+1, &sum).abs();
    return std::cmp::min(v1, v2);

    

}

// Search from [l, h)
// 答えは常に[l, h)の中にある。
// [l, h)の要素数が1ならl が答え。
fn binary_search(n: usize, sum:&[i32]) -> usize {
    let mut l:usize= 0;
    let mut h:usize = n - 1;
    while h - l > 1 {
        let mid = (l + h) / 2;
        //println!("{}, {} -> {}", l, h, mid);
        //println!("  diff={}", get_diff(n, mid, sum));
        if get_diff(n, mid, sum) <= 0 {
            l = mid;
        } else {
            h = mid;
        }
    }
    return l;
}

fn get_diff(n:usize, i:usize, sum:&[i32]) -> i32{
    return sum[i] - (sum[n-1] - sum[i]);
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {
    
    // source code
  string s;
  cin >> s;
  ll now = 0;
  ll imin = 0;
  ll total = 0;
  char nowc = ' ';
  map<ll,pair<char,ll>> smap;
  ll number = -1;
  rep(i,s.length())
  {
    if(s[i] != nowc)
    {
      number++;
      smap.insert(make_pair(number,make_pair(s[i],1)));
      nowc = s[i];
    }
    else
    {
      smap[number].second++;
    }
  }
  for( auto i = smap.begin(); i != smap.end() ; ++i ) {
    if(i != smap.begin())
    {
      if(i->second.first == '>')
      {
        --i;
        ll prev = i->second.second;
        ++i;
        if(prev < i->second.second)
        {
          total+=(i->second.second) * ((i->second.second) + 1) / 2;
          total-=prev;
          //cout << total << "Q" << endl;
        }
        else
        {
          total += (i->second.second) * ((i->second.second) - 1) / 2;
          //cout << total << "N" << endl;
        }
      }
      else
      {
        total+=(i->second.second) * ((i->second.second) + 1) / 2;
        //cout << total << "U" << endl;
      }
    }
    else
    {
      total += (i->second.second) * ((i->second.second) + 1) / 2;
      //cout << total << "K" << endl;
    }
  }
  cout << total << endl;
  //total -= imin * s.length();
  //cout << imin << endl;
  //cout << total;
}

Measured memory_bytes: 16388
#include<bits/stdc++.h>
using namespace std;
vector<int> visited;
vector<vector<int> > adj;
vector<int> parent;
vector<int> dp;
int main()
{
    int n,m;
    cin>>n>>m;
    adj.resize(n+1);
    visited.resize(n+1);
    parent.resize(n+1);
    dp.resize(n+1,1e7);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    dp[1]=0;
    visited[1]=1;
    while(!q.empty())
    {
        int s=q.front();
        q.pop();
        for(auto it:adj[s])
        {
            if(!visited[it])
            {
                visited[it]=1;
                q.push(it);
            }
            if(dp[it]>=dp[s]+1)
            {
                parent[it]=s;
                dp[it]=dp[s]+1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!visited[i])
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    for(int i=2;i<=n;i++)
    {
        cout<<parent[i]<<endl;
    }
}

Measured memory_bytes: 10944
#include<iostream>
#include<stdio.h>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
#include<queue>
#define rep(i,n) for(long int i=0;i<n;i++)
using namespace std;

int main(){
    long int N,M,K;
    cin>>N>>M>>K;
    vector<long int> A(M),B(M);
    vector<long int> C(K),D(K);
    vector<vector<long int> > f(N),nf(N);
    rep(i,M){
        cin>>A[i]>>B[i];
        f[A[i]-1].push_back(B[i]-1);
        f[B[i]-1].push_back(A[i]-1);
    }
    rep(i,K){
        cin>>C[i]>>D[i];
        nf[C[i]-1].push_back(D[i]-1);
        nf[D[i]-1].push_back(C[i]-1);
    }
    vector<bool> v(N,true);
    vector<long int> ans(N); 
    vector<long int> group(N,-1);
    rep(i,N){
        if (v[i]){
            v[i]=false;
            group[i]=i;
            queue<long int> que;
            vector<long int> num;
            que.push(i);
            num.push_back(i);
            while(!que.empty()){
                long int q=que.front();
                que.pop();
                rep(j,f[q].size()){
                    if (v[f[q][j]]){
                        group[f[q][j]]=i;
                        v[f[q][j]]=false;
                        que.push(f[q][j]);
                        num.push_back(f[q][j]);
                    }
                }
            }
            rep(j,num.size()){
                int a=0;
                rep(k,nf[num[j]].size()){
                    if (group[nf[num[j]][k]]==i) ++a;
                }
                ans[num[j]]=num.size()-f[num[j]].size()-1-a;
            }
        }
    }
    rep(i,N) cout<<ans[i]<<" ";
    cout<<endl;

    return 0;
}

Measured memory_bytes: 21784
import java.util.Scanner;

public class Main{
  public static void main(String ars[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int x = a + b;
    int y = a - b;
    int z = a * b;
    int max = Math.max(x,y);
    max = Math.max(max,z);  
    System.out.println(max);
  }
}

Measured memory_bytes: 21844
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    int A ,B, C, D, t_ans, b_ans;

    cin >> A >> B >> C >> D;
    t_ans = min(A, B);
    b_ans = min(C, D);

    cout << t_ans + b_ans;

    return 0;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
#define F first
#define S second
#define MK make_pair
const ll E=1e17+7;



int main(){
    int d[30][30]={};
    int a[3][30]={};
    int n,c;
    cin>>n>>c;
    for(int i=0;i<c;i++){
        for(int t=0;t<c;t++){
            cin>>d[i][t];
        }
    }
    for(int i=0;i<n;i++){
        for(int t=0;t<n;t++){
            int k;
            cin>>k;
            k--;
            a[(i+t)%3][k]++;
        }
    }
    ll mi=E;
    for(int i=0;i<c;i++){
        ll d1=0;
        for(int t=0;t<c;t++){
            if(t!=i){d1+=a[0][t]*d[t][i];}
        }
        for(int t=0;t<c;t++){
            if(t==i){continue;}
            ll d2=0;
            for(int k=0;k<c;k++){
                if(k!=t){d2+=a[1][k]*d[k][t];}
            }
            for(int k=0;k<c;k++){
                if(t==k || k==i){continue;}
                ll d3=0;
                for(int h=0;h<c;h++){
                    if(k!=h){d3+=a[2][h]*d[h][k];}
                }
                mi=min(d1+d2+d3,mi);
            }
        }
    }

    cout<<mi<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> cnt(3);
    for (auto &v : cnt)
        cin >> v;
    vector<pii> Q(n);
    for (auto &q : Q) {
        string s; cin >> s;
        q.F = s[0] - 'A';
        q.S = s[1] - 'A';
    }
    vector<char> ans;
    for (int i = 0 ; i < n - 1 ; i++) {
        if (cnt[Q[i].F] == 0 && cnt[Q[i].S] == 0) {
            cout << "No\n";
            return 0;
        }
        if (cnt[Q[i].F] != 0) {
            cnt[Q[i].F]--;
            cnt[Q[i].S]++;
            if (cnt[Q[i + 1].F] != 0 || cnt[Q[i + 1].S] != 0) {
                ans.push_back(char(Q[i].S + 'A'));
                continue;
            }
            cnt[Q[i].F]++;
            cnt[Q[i].S]--;
        }
        if (cnt[Q[i].S] != 0) {
            cnt[Q[i].S]--;
            cnt[Q[i].F]++;
            if (cnt[Q[i + 1].F] != 0 || cnt[Q[i + 1].S] != 0) {
                ans.push_back(char(Q[i].F + 'A'));
                continue;
            }
            cnt[Q[i].S]++;
            cnt[Q[i].F]--;
        }
        cout << "No\n";
        return 0;
    }
    if (cnt[Q.back().F] != 0) {
        cnt[Q.back().F]--;
        cnt[Q.back().S]++;
        ans.push_back(char(Q.back().S + 'A'));
    } else if (cnt[Q.back().S] != 0) {
        cnt[Q.back().F]++;
        cnt[Q.back().S]--;
        ans.push_back(char(Q.back().F + 'A'));
    } else {
        cout << "No\n";
        return 0;
    }
    cout << "Yes\n";
    for (auto &v : ans)
        cout << v << '\n';
}

Measured memory_bytes: 4356
#include <stdio.h>

int main(void) {
int a, b, c, tmp;

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

if(b < a) {
	tmp = a;
	a = b;
	b = tmp;
}

if(c < b) {
	tmp = b;
	b = c;
	c = tmp;
		if(b < a) {
			tmp = a;
			a = b;
			b = tmp;
		}
} 

printf("%d %d %d\n", a, b, c);

return 0;
}

Measured memory_bytes: 596
from sys import stdin


def main():
    lines = stdin.readlines()
    T = int(lines[0].split()[1])
    tn = [int(ti) for ti in lines[1].split()]
    print(tn[-1] + T - sum(t2 - t1 - T
                           for t1, t2
                           in zip(tn[0:], tn[1:]) if t2 - t1 > T))
    return


main()


Measured memory_bytes: 27200
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;

#define FOR(i, m, n) for(int i = (m);i < (n);i++)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;

int main() {
	int A, B, C, X;
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> X;

	int count = 0;
	for (int i = 0; i <= A; i++) {
		for (int j = 0; j <= B; j++) {
			for (int k = 0; k <= C; k++) {
				if (i * 500 + j * 100 + k * 50 == X) count++;

			}

		}

	}
	cout << count << endl;



	return 0;
}


Measured memory_bytes: 256
program ABC161B
    implicit none
    integer(8)::N,M,a_select,i,A_all
    integer(8),allocatable,dimension(:)::A
    read*,N,M
    allocate(A(N))
    read*,A
    a_select=0
    A_all=sum(A)

    do i=1,N
        if(4*M*A(i)>=A_all)a_select=a_select+1
    end do

    if(a_select>=M)then
        print'(A)',"Yes"
    else
        print'(A)',"No"
    end if
end program ABC161B

Measured memory_bytes: 512
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
gout = [[] for i in range(N)]
deg = [0] * N

for i in range(M):
    x, y = MAP()
    gout[x-1].append(y-1)
    deg[y-1] += 1
# only no_children 
topo = [v for v in range(N) if deg[v] == 0]
path_len = [0] * N
ans = 0
q = deque(topo)
# 子を持たない子スタート
while q:
    v = q.popleft()
    for t in gout[v]:
        # 親の子，vのカウントを減らす
        deg[t] -= 1
        # それでそれ以外の子がいなくなったら，
        # トポロジカルソートではスタックに積む
        if deg[t] == 0:
            q.append(t)
            path_len[t] = path_len[v] + 1
            ans = path_len[t]
print(ans)

Measured memory_bytes: 56880
import sys


def input():
    return sys.stdin.readline().rstrip()


def bitall(s, n):
    ans = 0
    for bit in range(1 << n):
        f = s[0]

        for i in range(n):
            if bit & (1 << i):
                f += "+"
            f += s[i + 1]

        ans += sum(map(int, f.split("+")))

    return ans


def main():
    s = input()
    n = len(s) - 1

    ans = bitall(s, n)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 41580
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char a,b,c;
 cin>>a>>b>>c;
 
 if(a==c){
 	cout<<"Yes"<<endl;
 }
 else {
 	cout<<"No"<<endl;
 }
  
 return 0;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

const int MAX_N = 1e6+10;
ll dp[MAX_N][2];


int main(){
    string s;
    cin >> s;    
    reverse(all(s));
    int n = s.size();
    REP(i, 1, n+2) rep(j, 2) dp[i][j] = INF;
    dp[0][1] = INF;
    rep(i, n) {
        int x = s[i] - '0';
        {
            //ちょうど払う
            chmin(dp[i+1][0], dp[i][0]+x);
            chmin(dp[i+1][0], dp[i][1]+x+1);
            //繰り上げる
            chmin(dp[i+1][1], dp[i][0]+10-x);
            chmin(dp[i+1][1], dp[i][1]+10-(x+1));

            // cout << i << " " << dp[i+1][0] << " " << dp[i+1][1] << endl;
        }
    }
    cout << min(dp[n][0], dp[n][1]+1) << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

int n;
const int nax = 2e5 + 10;
ll d[nax];

ll maxi(int k){
	ll s = 0;
	while(k > 0){
		s = max(d[k], s);
		k -= k & -k;
	}
	return s;
}

void add(int k, ll x){
	while(k <= n){
		d[k] = max(d[k], x);
		k += k&-k;
	}
}



int main(){
	cin >> n;
	ll h[n]; ll b[n];
	for (int i = 0; i < n; ++i) cin >> h[i];
	for (int i = 0; i < n; ++i) cin >> b[i];
	for(int i = 0; i < n; ++i){
		ll t = maxi(h[i] - 1);
		add(h[i], t + b[i]);
	}
	cout << maxi(n);
}

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

int main(){
	int n, x,count;
	while (1){
		count = 0;
		cin >> n >> x;
		if (n == 0 && x == 0)break;
		for (int i = 1; i <= n-2; i++){
			for (int j = i+1; j <= n-1; j++){
				for (int k = j+1; k <= n; k++){
						if (i+j+k == x){
							count++;
						}
					}
				}
			}
		cout << count << endl;
		}
		
	return 0;
}


Measured memory_bytes: 3088
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll X;
    cin >> X;
    ll N = 300000;
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;

    for (int i = 2; i * i <= N; i++) {
        if (is_prime[i] == true)
        {
            for (int j = 2; j * i <= N; j++) {
                is_prime[i * j] = false;
            }
        }
    }

    REP(x, X, N) {
        if (is_prime[x] == true) {
            cout << x << endl;
            return 0;
        }

    }

    return 0;
}

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

typedef long long LL;

int main() {
//    freopen("test.txt", "r", stdin);
    int n, a, b, c, d;
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    b = abs(b - a);
    bool flag = false;
    for (LL i = 0; i < n; i++) {
        LL left = c * (n - 1 - i) - d * i;
        LL right = d * (n - 1 - i) - c * i;
        if (left <= b && b <= right) {
            flag = true;
            break;
        }

    }
    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;

}

Measured memory_bytes: 256
//AOJ 4-1
#include<stdio.h>

int main(void) {

	int a = 0;	scanf("%d", &a);
	int b = 0;	scanf("%d", &b);

	printf("%d %d %lf\n", (a / b), (a % b), ((double)a / b));

	return 0;
}


Measured memory_bytes: 2108
#include<stdio.h>

int main(){
  int a,b,c,i,k=0;
  scanf("%d %d %d",&a,&b,&c);
  for(i=1;i<=100;i++){
      if((b*i+c)%a==0){
        printf("YES");
        k++;
        break;
      }
  }
  if(k==0)
    printf("NO");
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    ll a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    s[b - 1] += 32;
    cout << s << endl;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// 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 );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll x, y;
    cin >> x >> y;

    ll A = 0;
    ll B = 0;
    ll C = 0;

    if(x == 2){
        C++;
    }
    else if((x<8 && x%2 ==1) || (x>=8 && x%2 == 0)){
        A++;
    }
    else{
        B++;
    }

    if(y == 2){
        C++;
    }
    else if((y<8 && y%2 ==1) || (y>=8 && y%2 == 0)){
        A++;
    }
    else{
        B++;
    }

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

Measured memory_bytes: 3624
s = input()
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] in "RUD":
            pass
        else:
            print("No")
            exit()
    else:
        if s[i] in "LUD":
            pass
        else:
            print("No")
            exit()
print("Yes")

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int A,B,C;
int main(){
	cin>>A>>B>>C;
	for(int i=1;i<=1000000;i++){
		int P=i*A;
		if(P%B==C){cout<<"YES"<<endl;return 0;}
	}
	cout<<"NO"<<endl;
	return 0;
}


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

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  while(a>0 && c>0){
    a=a-d;
    c=c-b;
  }
  if(c<=0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3644
#include <stdio.h>

int main(void) {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a==b) {
	printf("a == b");
	} else if(a < b) {
		printf("a < b");
	} else {
		printf("a > b");
	}
	printf("\n");
	return 0;	
}

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

int main() { 
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    int left = a + b;
    int right = c + d;
    if (left > right) {
        cout << "Left" << endl;
    } else if (left < right) {
        cout << "Right" << endl;
    } else {
        cout << "Balanced" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	
	int h,w,n,bank = 0;
	scanf("%d %d %d" , &h, &w, &n);
	
	while (n > 0){
		
		if(h > w){
			n -= h;
		}
		else{
			n -= w;
		}
		bank++;
	}
	
	printf("%d" , bank);
	
	
	return 0;
}

Measured memory_bytes: 1736
#include <iostream>
#include <cstring>
using namespace std;
int main(void){
    // Your code here!
    int N;
    string S;
    cin>>N>>S;
    int c=1;
    for(int i=0;i<N-1;i++){
        if(S[i]!=S[i+1]){
            c++;
        }
    }
    cout<<c<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int n;

int main(){
	while(cin>>n){
		cout<<"3C";
		if(n%39==0)cout<<39<<endl;
		else{
			if(n%39<10)cout<<0;
			cout<<n%39<<endl;
		}
	}
}

Measured memory_bytes: 0
#include <iostream>
    #include <set>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <iomanip>
    #include <numeric>
    #include <cmath>
    #include <queue>
    #include <sstream>
     
    using namespace std;
    typedef long long ll;
     
    int main() {
      ll n, k;
      cin >> n >> k;
      
      vector<pair<ll,ll>> vec(n);
      for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        vec[i] = {b, a};
      }
      sort(vec.begin(), vec.end());
      reverse(vec.begin(), vec.end());
      
      set<ll> s;
      ll sum = 0;
      vector<ll> r;
      for (int i = 0; i < k; i++) {
        sum += vec[i].first;
        if (s.count(vec[i].second) == 0) {
          s.insert(vec[i].second);
        } else {
          r.push_back(vec[i].first);
        }
      }
      sum += s.size() * s.size();
      
      ll ans = sum;
      for (ll i = k; i < n; i++) {
        if (s.count(vec[i].second) == 0 && r.size() > 0) {
          sum -= r.back();
          sum -= s.size() * s.size();
          r.pop_back();
          
          sum += vec[i].first;
          s.insert(vec[i].second);
          sum += s.size() * s.size();
          ans = max(ans, sum);
        }
      }
      cout << ans << endl;
      return 0;
    }

Measured memory_bytes: 5244
#include <bits/stdc++.h> //library
#define rep(i, n) for(int i = 0; i < (int)(n); i++) //for-loop (from 0)
#define reps(i,n) for(int i = 1; i <= (int)(n); i++) //for-loop (from 1)
#define all(x) (x).begin(),(x).end() //start-to-end iteration, mainly in upper_bound, lower_bound
#define SZ(x) ((int)(x).size()) //unsigned to signed

using namespace std;
using ll = long long; //long long
ll M = 1000000000 + 7;
const ll INF = 1LL << 60;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } //compare a,b and replace by greater
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } //compare a,b and replace by smaller
ll qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; } //power
ll qp(int a, ll b, ll Mod) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%Mod; a = 1ll * a*a%Mod; } while (b >>= 1); return ans; } //power(mod)
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } //gcd
int dx[4] = { 1,0,-1,0 }; //path
int dy[4] = { 0,1,0,-1 }; //path
ll RS(ll N, ll P) { if (P == 0)return 1; else if (P % 2 == 0) { ll sq = RS(N, P / 2); return sq*sq; } else { return N*RS(N, P - 1); } } //power(repeat-square,fast)
ll nPr(ll n, ll r) { ll ans = 1; rep(i, r) { ans = ans * (n - i); } return ans; } //permutation
ll nCr(ll n, ll r) { ll bunbo = 1; ll bunshi = 1; rep(i, r) { bunbo = bunbo * (i + 1); bunshi = bunshi * (n - i); } return bunshi / bunbo; } //combination
ll RS(ll N, ll P, ll Mod) { if (P == 0)return 1; else if (P % 2 == 0) { ll sq = RS(N, P / 2, Mod); return sq*sq%Mod; } else { return N*RS(N, P - 1, Mod) % Mod; } } //power(mod)(repeat-square,fast)
ll nPr(ll n, ll r, ll Mod) { ll ans = 1; rep(i, r) { ans = ans * (n - i) % Mod; } return ans; } //permutation
ll nCr(ll n, ll r, ll Mod) { ll bunbo = 1; ll bunshi = 1; rep(i, r) { bunbo = bunbo * (i + 1) % Mod; bunshi = bunshi * (n - i) % Mod; } return bunshi * RS(bunbo, Mod - 2, Mod) % Mod; } //combination
int A[202000];

int main(void) {
  int K,N; cin >> K >> N;
  rep(i,N) cin >> A[i];
  ll dist = 0;
  rep(i,N-1) dist += A[i+1]-A[i];
  dist += (K+A[0])-A[N-1];
  ll res = INF;
  rep(i,N-1){
    chmin(res,dist-(A[i+1]-A[i]));
  }
  chmin(res,dist-((K+A[0])-A[N-1]));
  cout << res << endl;
}


Measured memory_bytes: 1024
package main

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

func main() {
	readLineInt()

	for _, v := range readLineInt() {
		if (v % 2) == 0 {
			if (v%3 != 0) && (v%5 != 0) {
				fmt.Println("DENIED")
				return
			}
		}
	}

	fmt.Println("APPROVED")
}

/////////////////////////////////////////

func readLineInt() []int {
	result := make([]int, 0)
	for _, v := range strings.Split(readLine(), " ") {
		i, _ := strconv.Atoi(v)
		result = append(result, i)
	}
	return result
}

var reader = bufio.NewReaderSize(os.Stdin, 1e6)

func readLine() string {
	result := make([]byte, 0, 1e6)
	for {
		line, remains, e := reader.ReadLine()
		if e != nil {
			panic(e)
		}
		result = append(result, line...)
		if !remains {
			break
		}
	}
	return string(result)
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned char ubyte;

const ld EPS = 1e-10;
const ld PI = acos(-1.0);
const int INF = (int)1e9 + 5;
const ll LINF = (ll)1e18 + 5;

template<class T> 
ll abs(const T & x) { return x < 0 ? -x : x; }

template<class T> 
ll round(const T & x) { return x < 0 ? x - 0.5 : x + 0.5; }

template<class T> 
bool chmin(T & x, const T & y) {
	if (y < x) {
		x = y;
		return true;
	}
	return false;
}

template<class T>
ostream & operator <<(ostream & os, const vector<T> & v) {
	os << "{";
	for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) {
		os << *it;
		if ((it + 1) != v.end()) os << ", ";
	}
	os << "}";
	return os;
}

template<class P, class Q>
ostream & operator <<(ostream & os, const pair<P, Q> & p) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template<class T> 
bool chmax(T & x, const T & y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

#define all(a) (a).begin(), (a).end()


int main() {
	srand(time(0));
#ifdef LOCAL 
	freopen("input.txt", "r", stdin);
#else
#endif

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

	vector<int> cnt(n, 1), was(n, 0);

	was[0] = 1;

	auto process = [&](int x, int y) {
		cnt[x]--;
		cnt[y]++;
		if (was[x]) {
			if (cnt[x] == 0) was[x] = 0;
			was[y] = 1;
		}
	};

	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		process(x, y);
	}
	
	int z = 0;

	for (int i = 0; i < n; i++) {
		if (was[i]) z++;
	}
	printf("%d\n", z);
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>

#include <inttypes.h>
using namespace std;

struct edge {
	int32_t from;
	int32_t to;
	int64_t cost;
};
static vector<struct edge> edges;
static vector<int64_t> d;
// 負のコストを持つ閉路を構成する辺の終点
static vector<bool> negative;

// bellman ford
// return false: 負のコストを持つ閉路が存在する。
static bool bellmanFord(int32_t start, int32_t nodeCnt, int32_t edgeCnt)
{
	for (int32_t i = 0; i < nodeCnt; i++)
		d[i] = numeric_limits<int64_t>::max();
	negative.resize(nodeCnt, false);

	d[start] = 0;
	bool negativeCostCircuitFound = false;
	for (int32_t i = 0; i < nodeCnt; i++) {
		for (int32_t j = 0; j < edgeCnt; j++) {
			struct edge e = edges[j];
			if (d[e.from] == numeric_limits<int64_t>::max())
				continue;

			if (d[e.to] > d[e.from] + e.cost) {
				if (i == nodeCnt - 1) {
					negative[e.to] = true;
					negativeCostCircuitFound = true;
				} else {
					d[e.to] = d[e.from] + e.cost;
				}
			}
		}
	}

	bool updated = negativeCostCircuitFound;
	while (updated) {
		updated = false;
		for (int32_t j = 0; j < edgeCnt; j++) {
			struct edge e = edges[j];
			if (negative[e.from] && !negative[e.to]) {
				negative[e.to] = true;
				updated = true;
			}
		}
	}

	return !negativeCostCircuitFound;
}

int main()
{
	int32_t nodeCnt, edgeCnt;
	scanf("%d%d", &nodeCnt, &edgeCnt);

	d.resize(nodeCnt);
	edges.resize(edgeCnt);
	for (int32_t i = 0; i < edgeCnt; i++) {
		int32_t a, b;
		int64_t c;
		scanf("%d%d%" PRId64, &a, &b, &c);
		a--;
		b--;
		c = -c;

		edges[i].from = a;
		edges[i].to = b;
		edges[i].cost = c;
	}

	bool valid = bellmanFord(0, nodeCnt, edgeCnt);
	if (!valid && negative[nodeCnt - 1])
		printf("inf\n");
	else
		printf("%" PRId64 "\n", -d[nodeCnt - 1]);

	return 0;
}

Measured memory_bytes: 256
//
//  string_formation.cpp
//  learningCplusplus
//
//  Created by Tran Duc Chinh on 2020/04/04.
//  Copyright © 2020 Tran Duc Chinh. All rights reserved.
//

#include <iostream>
#include <string>
#include<algorithm>
typedef long long ll;
int main(int argc, const char* argv[]) {
  std::string s;
  int q;
  std::cin >> s;
  std::cin >> q;

  int reverse_time = 0;

  for (int i=0; i<q; i++) {
    int t;
    int f;
    char c;
    std::cin >> t;
    if (t == 1) {
      // std::reverse(s.begin(), s.end());
      reverse_time += 1;
    }
    else if (t == 2) {
      std::cin >> f;
      std::cin >> c;
      if (f == 1) {
        if (reverse_time % 2 == 0) {
          s.insert(s.begin(), 1, c);
        }
        else {
          s.push_back(c);
        }
      }
      else if (f == 2) {
        if (reverse_time % 2 == 0) {
          s.push_back(c);
        }
        else {
          s.insert(s.begin(), 1, c);
        }
      }
    }

  }
  if (reverse_time % 2 == 1) {
    std::reverse(s.begin(), s.end());
  }
  std::cout << s << std::endl;
}

Measured memory_bytes: 900
#もらうDP
N = int(input())
dp=[float('inf')]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6 = 1
    pow9 = 1
    while pow6 <= n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
 
int main()
{int k,n,i;
cin>>k;
 string s;
 cin>>s;
 
 n=s.size();
 
 if(n<=k)
 cout<<s;
 
 else{
 	for(i=(n-1);i>(k-1);i--)
 	s.pop_back();
 	
 	cout<<s<<"...";
 }
 
}
    

Measured memory_bytes: 3636
/* ABC-A.c
   Yuta Takayanagi */

#include<stdio.h>
int main(void){
    int x, y;
    double width, height, area;

    area = 0;

    scanf( "%lf %lf %d %d" , &width, &height, &x, &y);
    /* 長方形の幅、高さと点の座標を入力 */

    area = (width * height) /2; /* 長方形の面積を求める */

    printf( "%f " , area);
    /* 長方形の中心を通る時、半分となり大きくない方の最大となる
       これは点がどこであっても存在する。 */

    if(2*x==width && 2*y==height){
    /* 点が長方形の中心と一致する時条件を満たす直線は無限に存在する */

        printf( "1\n" );

    }else{

        printf( "0\n" );

    }

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll A,B,K;
    cin>>A>>B>>K;
    if(A-K>=0){
        cout<<A-K<<" "<<B<<endl;
    }else{
        cout<<0<<" "<<max(0LL,B+(A-K))<<endl;
    }
}

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

int gcd(long long a, long long b){
  long long M = max(a, b), m = min(a, b);
  while(m != 0){
  	long long r = M%m;
    M = m; m = r;
  }
  return M;
}

int digit_sum(long long n){
  long long ans;
  while(n != 0){
  	ans += n%10;
  	n /= 10;
  }
  return ans;
}

int main(){
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for(int i = 0; i < 3; i++){
  	if(s.at(i) == t.at(i)){
    	ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

m = 0
for i in range(N):
    if A[i] >= B[i]:
        m += B[i]
    else:
        m += A[i]
        if A[i+1] >= (B[i]-A[i]):
            m += (B[i]-A[i])
            A[i+1] -= (B[i]-A[i])
        else:
            m += A[i+1]
            A[i+1] = 0
        
print(m)

Measured memory_bytes: 25596
n = int(input())
zahyou = []
for i in range(n):
    a = input().split()
    zahyou.append(a)
import math


def distance(x1,x2,y1,y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

allen = 0
for i in zahyou:
    for j in zahyou:
        allen += distance(int(i[0]),int(j[0]),int(i[1]),int(j[1]))

ans = float(allen/n)
print(ans)

Measured memory_bytes: 3064
// AOJ 2408

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(void)
{
	int n, k;
	vector < vector <int> > boat;
	
	cin >> n >> k;
	for (int i = 0; i < k; i++){
		int m; cin >> m;
		vector <int> jap(m);
		for (int j = 0; j < m; j++) cin >> jap[j];
		boat.push_back(jap);
	}
	
	int r, a, b;
	cin >> r;
	bool ng[55][55];
	for (int i = 0; i < 55; i++) fill (ng[i], ng[i] + 55, false);
	for (int i = 0; i < r; i++){
		cin >> a >> b;
		ng[a][b] = ng[b][a] = true;
	}
	
	map <int, int> ret;
	for (int i = 0; i < k; i++){
		for (int j = 0; j < boat[i].size(); j++){
			for (int k = 0; k < boat[i].size(); k++){
				a = boat[i][j], b = boat[i][k];
				if (ng[a][b] == true){
					ret[a] = 1;
					ret[b] = 1;
					ng[a][b] = ng[b][a] = false;
				}
			}
		}
	}
	
	cout << ret.size() << endl;
	
	return 0;
}

Measured memory_bytes: 1220
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long W;
  scanf("%lld", &W);
  std::vector<long long> w(N);
  std::vector<long long> v(N);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &w[i]);
    scanf("%lld", &v[i]);
  }
  vector<ll> dp(2 * W, 0);
  for (int i = 0; i < N; ++i)
  {
    for (int j = W; j >= w[i]; --j)
    {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  cout << dp[W] << endl;

  return 0;
}


Measured memory_bytes: 1792
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const int L = 10 * 1000 + 7;
const int S = 107;
const int MOD = 1000 * 1000 * 1000 + 7;

void add(int& x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int f[L][S][2];

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
    string s;
    cin >> s;
    int n = s.size();
    int d;
    cin >> d;
    f[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            for (int k = 0; k < 2; k++) {
                int r = 9;
                if (k == 0) {
                    r = s[i] - '0';
                }
                for (int cd = 0; cd <= r; cd++) {
                    int gk = k;
                    if (cd < s[i] - '0') {
                        gk = 1;
                    }
                    add(f[i + 1][(j + cd) % d][gk], f[i][j][k]);
                }
            }
        }
    }

    int ans = (f[n][0][0] + f[n][0][1]) % MOD;
    ans = (ans + MOD - 1) % MOD;
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL x,n,c;
int main(){
  	LL max = 1e18;
	cin>>n;
  	c = 1ll;
  	for (int i=1;i<=n;i++){
    	cin>>x;
      	if (1.0 * max / c >= 1.0 * x) c *= x; else c = max + 8762;
    	if (c == 0) break;
    }
  	if (c > max) cout<<"-1"<<endl; 
  	else cout<<c<<endl;
  	return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define mod 1000000007ll
	#define sz 20101010
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll fac[sz],_fac[sz];
void init()
{
	fac[0]=_fac[0]=fac[1]=_fac[1]=1;
	for(int i=2;i<sz;i++) fac[i]=1LL*fac[i-1]*i%mod,_fac[i]=1LL*(mod-mod/i)*_fac[mod%i]%mod;
	for(int i=2;i<sz;i++) _fac[i]=1LL*_fac[i]*_fac[i-1]%mod;
}
ll C(int n,int m) {return n>=m&&m>=0?1LL*fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int main()
{
	file();
	ll H,W,K;read(H,W,K);
	ll ans=0;
	init();
//	rep(i,1,K) rep(j,0,min(i,W)) (ans+=fac[i]*(j+1)%mod*(i-j+1)%mod*C(W+H-i,K-i)%mod*fac[K-i]%mod*C(W,j)%mod*C(H,i-j)%mod)%=mod;
	rep(i,1,K) (ans+=fac[i]*C(W+H-i,K-i)%mod*fac[K-i]%mod*(W*H%mod*C(W+H-2,i-2)%mod+(W+H)*C(W+H-1,i-1)%mod+C(W+H,i))%mod)%=mod;
	cout<<ans;
	return 0; 
}


Measured memory_bytes: 315648