akhauriyash/Code-Regression huggingface dataset:
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let N = read!(usize);
    let mut A = read![[i64]];

    A.sort();

    let mut count = 0;

    for i in 0..N {
        let a = A[i];
        let mut u = 0;

        for j in i + 1..N {
            let b = A[j];

            while u < N && A[u] < a + b {
                u += 1;
            }

            count += u.saturating_sub(j + 1);
        }
    }

    println!("{}", count)
}


Measured memory_bytes: 4352
n, h = map(int, input().split())

A, B = [], []
for _ in range(n):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

max_A = max(A)
BB = [B[i] for i in range(n) if B[i] > max_A]
BB.sort(reverse=True)

cnt = 0
for i in range(len(BB)):
	if h <= 0: #forgot equal... 
		print(cnt)
		exit()
	h -= BB[i]
	cnt += 1

# additional attack
if h % max_A == 0:
	cnt += h // max_A
else:
	cnt += h // max_A + 1

print(cnt)


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

int k,n,ans;
string s;

int calc1();
int calc2();
int calc3();

int calc1(){
	int a;
	a=calc2();
	while(s[k]=='+' ||s[k]=='-'){
		if(s[k]=='+'){
			k++;
			a+=calc2();
		}else if(s[k]=='-'){
			k++;
			a-=calc2();
		}
	}
	return a;
}

int calc2(){
	int a;
	a=calc3();
	while(s[k]=='*' ||s[k]=='/'){
		if(s[k]=='*'){
			k++;
			a*=calc3();
		}else if(s[k]=='/'){
			k++;
			a/=calc3();
		}
	}
	return a;
}

int calc3(){
	int a;
	if(s[k]=='('){
		k++;
		a=calc1();
		k++;
	}else{
		a=0;
		while(s[k]>='0' && s[k]<='9'){
			a*=10;
			a+=s[k]-'0';
			k++;
		}
	}
	return a;
}

int main(){
	cin >> n;
	while(n--){
		ans=0;
		k=0;
		cin >> s;
		ans=calc1();
		cout << ans <<endl;
		s.clear();
	}
	return 0;
}

Measured memory_bytes: 3148
#include<iostream>
#include<queue>
#include<bitset>
#include<algorithm>
#include<climits>
#include<deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define fill(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define dump(a) rep(i,a.size()){ cout<<a[i]<<" "; } cout<<endl;
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define INF INT_MAX/3
#define EPS 1e-7

// 各桁の和(point)を枝の重みとしたグラフを考える
// 求めるのは1~K(mod Kで0)の整数を点として、+1(重み1),x10(重み0)の遷移を枝としたグラフ上の、1->0の最短経路
// modKで同一視して良いのは、iとi+mKの遷移先がmodKとして同じになるからで、iとi+mKのグラフは同一視できるから
// 9+1で10になる遷移は、明らかに最短でないから最短経路には影響しない。
// dijkstra, BFSでもなく, 01BFSを使うとO(K)で求まる

int digitsum(ll n) {
  ll t = n;
  ll s = 0;
  while(t>0){
    s += t % 10;
    t = t / 10;
  }
  return s;
}

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

  deque<P> d;
  d.push_front(P(1,1)); // n, cost
  vector<bool> visited(k,false);

  while(!d.empty()){
    P p = d.front(); d.pop_front();
    int i=p.first, score=p.second;
    if(i==0) {
      cout<<score<<endl;
      break;
    }
    visited[i]=true;
    // 遷移
    ll n0 = (i*10)%k;
    ll n1 = (i+1)%k;
    if(!visited[n0]) d.push_front(P(n0, score));
    if(!visited[n1]) d.push_back(P(n1, score+1));
  }
  return 0;
}




Measured memory_bytes: 768
#include <cstdio>
#include <algorithm>
#include <deque>

#define fi first
#define se second
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int Inf = 0x3f3f3f3f;
const int MN = 505;

int N, A[MN][MN], P[MN * MN];
inline void g(int x, int &i, int &j) {
	i = (x - 1) / N + 1;
	j = (x - 1) % N + 1;
}

std::deque<std::pair<int, int>> q;
int D[MN][MN], Ans;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j) {
			A[i][j] = 1;
			D[i][j] = std::min({i - 1, N - i, j - 1, N - j});
		}
	for (int i = 1; i <= N * N; ++i) {
		int pos, x, y;
		scanf("%d", &pos);
		g(pos, x, y);
		Ans += D[x][y];
		A[x][y] = 0;
		q.push_back({x, y});
		while (!q.empty()) {
			auto p = q.front(); q.pop_front();
			int ux = p.fi, uy = p.se;
			for (int d = 0; d < 4; ++d) {
				int vx = ux + dx[d], vy = uy + dy[d];
				if (vx < 1 || vx > N || vy < 1 || vy > N) continue;
				if (D[vx][vy] > D[ux][uy] + A[ux][uy]) {
					D[vx][vy] = D[ux][uy] + A[ux][uy];
					A[ux][uy] ? q.push_back({vx, vy}) : q.push_front({vx, vy});
				}
			}
		}
	}
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 5796
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, H, W;
    cin >> N >> H >> W;
    cout << (N-(H-1)) * (N-(W-1)) << '\n';
}


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

const int INF = 1000000000;

int main() {
    int n, m; cin >> n >> m;
    tuple<int, int, int> e[m];
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        e[i] = make_tuple(a, b, c);
    }
    int d[n][n];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = INF;
    for (int i = 0; i < n; i++) { //各頂点から考える
        d[i][i] = 0;
        bool update = true;
        while (update) {
            update = false;
            for (int j = 0; j < m; j++) {
                int a, b, c;
                tie(a, b, c) = e[j];
                if (d[i][a] > d[i][b] + c) {
                    d[i][a] = d[i][b] + c;
                    update = true;
                }
                if (d[i][b] > d[i][a] + c) {
                    d[i][b] = d[i][a] + c;
                    update = true;
                }
            }
        }
    }
    bool used[m];
    for (int i = 0; i < m; i++) used[i] = false;
    for (int i = 0; i < n; i++) { //各頂点から考える
        for (int j = 0; j < m; j++) { //頂点iからの最短経路に辺jが使われるか
            if (used[j]) continue;
            int a, b, c;
            tie(a, b, c) = e[j];
            for (int k = 0; k < n; k++) { //頂点iからkへの最短経路について
                if (d[i][k] == d[i][a] + c + d[b][k] || d[i][k] == d[i][b] + c + d[a][k]) {
                    used[j] = true;
                    break;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (!used[i]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a[3];
    for(int i = 0; i < 3; ++i) cin >> a[i];
    sort(a, a+3);
    int k; cin >> k;
    int ans = 0;
    for(int i = 0; i < 3; ++i){
        if(i == 2) for(int j = 0; j < k; ++j) a[i] *= 2;
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
const int INF=1000010000;
typedef long long ll;
int main() {
  int n;cin >> n;
  vector<ll> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<vector<ll>> dp(3100,vector<ll>(3100,0));
  for(int len=1; len<=n; len++){
    for(int i=0; i+len<=n; i++){
      int j=i+len;
      if((n-len)%2==0) dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j-1]);
      else dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j-1]);
    }
  }
  cout << dp[0][n] << endl;
  return 0;
}

Measured memory_bytes: 75520
n, m = [int(i) for i in input().split()]

num = ['0']*n
l = [0]*n
b = 0
for i in range(m):
  s, c = input().split()
  s = int(s)-1
  if l[s] == 0 or num[s] == c:
    num[s] = c
    l[s] = 1
  else:
    b += 1
    break

if n >= 2 and l[0] == 1 and num[0] == '0':
  b += 1
elif n >= 2 and l[0] == 0 and num[0] == '0':
  num[0] = '1'

if b == 0:
  num = ''.join(num)
  print(int(num))
else:
  print(-1)


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        int s = scan.nextInt();

        int count = 0;

        for(int x = 0; x <=  s; x++) {
            if(x <= k) {
                for(int y = 0; y <= s - x; y++) {
                    if (y <= k && s - x - y <= k){
                        count += 1;
                    }
                }
            }
        }
        System.out.println(String.valueOf(count));

    }
}

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

int main(){
  ll n,k,i,t,c,d,e,l;
  cin >> n >> k;
  ll a[n+1],b[n+1],f[n+1];
  for(i=1;i<=n;i++){
    cin >> a[i];
    b[i]=-1;
  }
  b[1]=0;
  c=1;
  f[0]=1;
  for(i=1;i<=n;i++){
    t=a[c];
    c=t;
    f[i]=t;
    if(b[t]==-1){
      b[t]=i;
    }
    else{
      d=b[t];
      e=i;
      break;
    }
  }
  if(e<k){
    k-=d;
  	l=k%(e-d);
  	cout << f[d+l];
  }
  else{
    cout << f[k];
  }
}

Measured memory_bytes: 8024
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll dp[10000];
ll N, T;
ll A[3030], B[3030];
Pll AB[3030];

int main() {
  cin >> N >> T;
  rep(i, 0, N) {
    cin >> A[i] >> B[i];
    AB[i] = Pll(A[i], B[i]);
  }
  sort(AB, AB + N);

  rep(i, 0, N) {
    for (int j = T - 1; j >= 0; --j) {
      assert(j + A[i] < 10000);
      chmax(dp[j + AB[i].first], (dp[j] + AB[i].second));
    }
  }

  ll ans = 0;
  repe(i, 0, T + 3000) { chmax(ans, dp[i]); }

  cout << ans << endl;
}


Measured memory_bytes: 3748
import math

class Debt(object):
    def __init__(self):
        self.debt = 100000
        
    def spend_a_week(self):
        self.debt = self._ceil_1000(self.debt * 1.05)

    def _ceil_1000(self, debt):
        return int(math.ceil(debt / 1000) * 1000)

def run():
    n = int(input())
    debt = Debt()
    for _ in range(n):
        debt.spend_a_week()
    print(debt.debt)

if __name__ == '__main__':
    run()




Measured memory_bytes: 5672
//問題URL
//

//解き方メモ
//
    
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define A (abc[0])
#define B (abc[1])
#define C (abc[2])

int main(){
  int n;

  //input
  cin >> n;
  vector< vector<long long> > abc(3,vector<long long>(n));
  vector< vector<long long> > a,b,c;

  for(int i=0;i<3;i++){
    for(int j=0;j<n;j++){
      cin >> abc[i][j];
    }
    sort(abc[i].begin(),abc[i].end());
  }

  long long result = 0;
  for (int i = 0; i < n; i++) {
    long long a_cnt = lower_bound(A.begin(),A.end(),B[i]) - A.begin();
    long long b_cnt = C.size() - (upper_bound(C.begin(),C.end(),B[i]) - C.begin());

    result += a_cnt * b_cnt;
  }

  cout << result << endl;
  
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'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'};
char moji2[26]={'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'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}


struct MAT{
    int mat[55][55];
};
MAT mul(MAT &a,MAT &b,int mat_size){
    MAT c;
    REP(i,mat_size){
        REP(j,mat_size){
            c.mat[i][j]=0;
            REP(k,mat_size)(c.mat[i][j]+=a.mat[i][k] * b.mat[k][j]), c.mat[i][j] %= MOD;
        }
    }
    return c;
}

signed main(){
    int n,k;
    cin >> n >>k;
    MAT x,ans;
    REP(i,n) REP(j,n) cin >> x.mat[i][j];
    REP(i,n) REP(j,n){
        if(i == j) ans.mat[i][j] = 1;
        else ans.mat[i][j] = 0;
    }

    int beki = 1;
    int mask = 1;
    while(mask <= k){
        if( (mask & k) ){
            ans = mul(x,ans,n);
        }
        beki ++;
        mask *= 2;
        x = mul(x,x,n);
    }

    int res = 0;
    REP(i,n) REP(j,n) res += ans.mat[i][j], res %= MOD;
    cout << res << endl;

}

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

int		main(void)
{
	int n;

	cin >> n;
	vector<int> house(n);

	for(int i = 0; i < n; i++)
		cin >> house[i];
	sort(house.begin(), house.end());
	cout << (house[n - 1] - house[0]) << endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::cmp::*;

fn main() {
    let n: usize = read();
    let w: i64 = read();
    let v: usize = 10_usize.pow(5);
    let wv: Vec<(i64, usize)> = (0..n).map(|_| (read(), read())).collect();
    let inf: i64 = 1_i64 << 60;

    // dp[i][value] = weight_min
    let mut dp: Vec<Vec<i64>> = vec![vec![inf; v+1]; n+1];
    dp[0][0] = 0;
    for i in 0..n {
        let (wi, vi) = wv[i];
        for j in 0..v+1 {
            if j >= vi {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - vi] + wi);
            }
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
    }
    let mut ans = 0;
    for i in 0..v+1 {
        if dp[n][i] <= w {
            ans = max(ans, i);
        }
    }
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 106876
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 11 11:57:24 2020

@author: liang
"""

H, W = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1
sx -= 1
gy, gx = map(int, input().split())
gy -= 1
gx -= 1
field = [input() for _ in range(H)]

from collections import deque
q = deque()
adj1 = [(0,1), (0,-1), (1,0), (-1,0)]
visited = [[False]*W for _ in range(H)]

q.append((sy, sx, 0))

while q:
    cy, cx, cost = q.popleft()
    #print(cy,cx,cost)
    if (cy,cx) == (gy,gx):
        print(cost)
        break
    if not visited[cy][cx]:
        #print("visit!")
        visited[cy][cx] = True
        #cost 0
        for a in adj1:
            ny, nx = cy + a[0], cx + a[1]
            if ny >= H or ny < 0:
                continue
            if nx >= W or nx < 0:
                continue
            if field[ny][nx] == "#":
                continue
            if not visited[ny][nx]:
                q.appendleft((ny, nx, cost))
        #cost 1
        for i in range(-2,3):
            for j in range(-2,3):
                ny, nx = cy + i, cx + j
                if ny >= H or ny < 0:
                    continue
                if nx >= W or nx < 0:
                    continue
                if field[ny][nx] == "#":
                    continue
                if not visited[ny][nx]:
                    q.append((ny, nx, cost+1))
else:
    print(-1)

Measured memory_bytes: 189396
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.next());
        int n = Integer.parseInt(sc.next());
        int[] a = new int[n];
        int sub = 0;
        int bef = 0;
        int temp = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            temp = Integer.parseInt(sc.next());
            if (i != 0) {
                ans += temp - bef;
                sub = Math.max(sub, temp - bef);
            }
            if (i == n - 1) {
                ans += Math.abs(k - temp + a[0]);
                sub = Math.max(sub, Math.abs(k - temp + a[0]));
            }
            bef = temp;
            a[i] = temp;
        }
        System.out.println(ans - sub);
    }
}


Measured memory_bytes: 59548
#include <cstdio>
long long int n,m;
long long int t[11111111];
int main(void){
  scanf("%lld",&n);
  t[0] = n;
  for(int i = 0; i < n; i++){
    long long int h;
    scanf("%lld",&h);
    t[h] -= 1;
  }

  long long int res = 1;
  m = 4;
  for(int i = 0; t[i]; i++){
    res += (m>t[i])?t[i]:m;
    m += 4;
    t[i+1] += t[i];
  }
  printf("%lld\n",res);
}

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

using namespace std;
using std::vector;

#define ll long long
#define vi  vector<int>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD int(1e9) + 7
#define PAI  3.1415926535
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i,n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b != 0) gcd(b, a%b);
  return b;
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a / gcd(a , b)) * b;
}

int main(){
 
  vi v(5, 0);
  rep(i, 5) cin >> v[i];
  int pos = 0;
  int mini = 9;

  rep(i, 5){
    if(mini > v[i] % 10 and v[i] % 10 != 0){
      pos = i;
      mini = v[i] % 10;
    }
  }

  int ans = v[pos];

  rep(i, 5){
    if(pos == i)
      continue;
    if(v[i] % 10 == 0)
      ans += v[i];
    else
    {
      ans += (v[i] / 10 + 1) * 10;
    }
    
  }
  pr(ans);

  return 0;
}


Measured memory_bytes: 256
def main():
   A, B, C, K = map(int, input().split())

   if K < A:
        print(1 * K)
   elif A + B >= K:
        print(1 * A)
   else:
        value = A + (-1 * (K -A -B))
        print(value)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)

Measured memory_bytes: 39852
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod 1000000007
#pragma GCC optimize ("-O2")
#define mod2 998244353
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector <vector <int>>
#define v4096 vector <vector <lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli,lli>
#define m32 map<int,int>
#define m64it map<lli,lli>::iterator
#define m32it map<int,int>::iterator
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ist insert
#define endl "\n"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<pair<lli,int>, null_type,less<pair<lli,int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define p_q priority_queue 
#define min_p_q priority_queue <int,vt <int>,greater <int>>
using namespace std;
using namespace __gnu_pbds; 
template <typename T> 
void DEBUG_ARR(vt<T> a){
	f(i,0,a.size())cout<<a[i]<<" ";
	cout<<"\n";
}

int main() { 
    fastio;
    int a,b;
    cin>>a>>b;
    cout<<6-a-b<<"\n";
    return 0; 	
}

Measured memory_bytes: 892
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

struct nap{
	int ct,v;
	nap(){}
	nap(int ct,int v):ct(ct),v(v){}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
	int n,W;
	cin>>n>>W;
	vector<nap> dp(40003,nap(0,0));
	vector<pair<int,int >> wv(n);
	REP(i,n)cin>>wv[i].first>>wv[i].second;
	int w1 = wv[0].first;
	if(w1 > 300){

		int wct = W/w1;
		int newW = min(305,W%w1);
		REP(i,n)wv[i].first-=w1;
		sort(wv.begin(),wv.end(),greater<pair<int,int> >());
		REP(i,n){
			for(int j = newW-wv[i].first;j >=0;j--){
				if(dp[j].ct<wct){
					if((dp[j+wv[i].first].v < dp[j].v + wv[i].second && dp[j+wv[i].first].ct == dp[j].ct+1) || (dp[j+wv[i].first].ct-1 < dp[j].ct)){
						dp[j+wv[i].first].v = dp[j].v + wv[i].second;
						dp[j+wv[i].first].ct = dp[j].ct + 1;
					}
				}
			}
		}
		ll ans = 0;
		REP(i,newW + 1){
			ans = max((ll)dp[i].v,ans);
		}
		cout << ans << endl;
	}else{
		if(W > 400*100)W = 400*100;
		REP(i,n){
			for(int j = W-wv[i].first;j >=0;j--){
				if(j == 0 || dp[j].v>0)
				dp[j+wv[i].first].v = max(dp[j+wv[i].first].v,dp[j].v + wv[i].second);
			}
		}

		int ans = 0;
		REP(i,W+1){
			ans = max(dp[i].v,ans);
		}
		cout << ans << endl;
	}
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define fr(i,x,y) for(int i=x;i<=y;++i)
#define rf(i,x,y) for(int i=x;i>=y;--i)
#define LL long long
using namespace std;
const int N=5010,mod=1e9+7;
char lx[N];
LL dp[N][N];

void Mul(LL &x,LL y){
	x=(x*y)%mod;
}

void Add(LL &x,LL y){
	x=(x+y)%mod;
}

LL mul(LL x,LL y){
	return x*y%mod;
}

LL add(LL x,LL y){
	return (x+y)%mod;
}

LL q_pow(LL x,int y=mod-2){
	LL ans=1;
	for(;y;y>>=1){
		if(y&1) Mul(ans,x);
		Mul(x,x);
	}
	return ans;
}

int main(){
	int k;scanf("%d",&k);
	scanf("%s",lx+1);
	int n=strlen(lx+1);
	dp[0][0]=1;
	fr(i,1,k) fr(j,0,i){
		if(j) Add(dp[i][j],mul(dp[i-1][j-1],2));
		else Add(dp[i][j],dp[i-1][j]);
		Add(dp[i][j],dp[i-1][j+1]);
		//printf("%d %d %lld\n",i,j,dp[i][j]);
	}
	LL pos=1;
	fr(i,1,n) Mul(pos,2);
	LL ans=mul(dp[k][n],q_pow(pos));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 194176
import math


inputa = input().split()
inputb = input().split()

a = int(inputa[0])
b = int(inputa[1])
# c = int(inputa[2])

# x = int(inputb[0])
# y = int(inputb[1])

# inputList=[]
# for i in range(a):
#     inputNum = input()
#     inputList.append(inputNum)

listb = []
listb = [int(n) for n in inputb]

sum = 0
cnt = 0

for i in range(a):
    sum += listb[i]
    if sum <= b:
        cnt = i + 2
    else:
        break

print(cnt)


Measured memory_bytes: 38384
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int a[3], b[3];
int m[4][4];
int main(void) {
    REP(i, 3) {
        int a, b;
         cin >> a >> b;
         a--;b--;
         m[a][b] = m[b][a] = 1;
    }
    VI v(4);
    iota(ALL(v), 0);
    do {
        bool ok = true;
        REP(i, 3) {
            if (!m[v[i]][v[i + 1]]) ok = false;
        }
        if (ok) {
            cout << "YES" << endl;
            return 0;
        }
    } while (next_permutation(ALL(v)));
    cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <vector>

int main() {
	int N;
	std::cin>>N;
	int W;
	std::cin>>W;
	std::vector<int> weight(N);
	std::vector<int> value(N);
	for (int i = 0; i < N * 2; ++i) {
		int h;
		std::cin >> h;
		if (i % 2 == 0) {
			weight[i/2] = h;
		} else {
			value[i/2] = h;
		}
	}

	uint64_t A[N+1][W+1];
	for (int i = 0; i <= W; ++i) {
		A[0][i] = 0;
	}

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j <= W; ++j) {
			//printf("weight[%d] i[%d] j[%d]\n", weight[i-1], i, j);
			if (weight[i-1] > j) {
				A[i][j] = A[i-1][j];
			} else {
				A[i][j] = std::max(A[i-1][j], value[i-1] + A[i-1][j-weight[i-1]]);
			}
			//printf("pre[%d] total weight[%d] value[%llu]\n", i, j, A[i][j]);
		}
	}
	printf("%llu\n", A[N][W]);
	return 0;
}


Measured memory_bytes: 79104
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int[][] field = new int[h][w];

    for (int i = 0; i < h; i++) {
      String s = sc.next();
      for (int j = 0; j < w; j++) {
        if (s.charAt(j) == '#') {
          field[i][j] = Integer.MIN_VALUE;
          if ((i - 1) >= 0) {
            field[i - 1][j]++;
            if ((j - 1) >= 0) {
              field[i - 1][j - 1]++;
            }
            if ((j + 1) < w) {
              field[i - 1][j + 1]++;
            }
          }

          if ((j - 1) >= 0) {
            field[i][j - 1]++;
          }

          if ((j + 1) < w) {
            field[i][j + 1]++;
          }

          if ((i + 1) < h) {
            field[i + 1][j]++;
            if ((j - 1) >= 0) {
              field[i + 1][j - 1]++;
            }
            if ((j + 1) < w) {
              field[i + 1][j + 1]++;
            }
          }

        }
      }
    }

    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        if (field[i][j] < 0) {
          System.out.print('#');
        } else {
          System.out.print(field[i][j]);
        }
      }
      System.out.println();
    }

  }
}

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

const ll inf = 1e10;

int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> h(n);
	for (ll i = 0; i < n; ++i)cin >> h[i];
	vector<ll> dp(n, inf);
	dp[0] = 0;
	for (ll i = 0; i < n; ++i) {
		for (ll j = i + 1; j <= min(n - 1, i + k); ++j) {
			dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
		}
	}
	cout << dp.back() << endl;
}


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

int main(int argc, char *argv[])
{
  int h, w;
  while((cin >> h >> w) && (h != 0 && w != 0)) {
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
        cout << '#';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3104
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<stack>
#include<set>
#include<string.h>
#include<map>
#include<vector>
#define pb push_back
#define ins insert 
#define mp make_pair
#define ll long long 
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define M 10000007
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    ll a[n+1],dp[n+1];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i+1];
        dp[i+1]=0;
    }
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for (int i = 3; i <n+1; ++i)
    {
        dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]));
    }
    cout<<dp[n];

    return 0 ;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <algorithm>  
#include <unordered_set>

#define ll long long

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	char s;
	cin >> s;

	if (s >= 'a' && s <= 'z') {
		cout << "a" << endl;
	}
	else if(s >= 'A' && s <= 'Z'){
		cout << 'A' << endl;
	}

	return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

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

int main() {
    int N, M;
    map<string, int> blue, red;

    cin >> N;
    for (int i = 0; i < N; i++) {
        string temp;
        cin >> temp;
        auto itr = blue.find(temp);
        if (auto itr = blue.find(temp) != blue.end()) blue[temp]++;
        else blue[temp] = 1;
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        string temp;
        cin >> temp;
        auto itr = red.find(temp);
        if (auto itr = red.find(temp) != red.end()) red[temp]++;
        else red[temp] = 1;
    }

    int maximum = 0;

    for (auto itr = blue.begin(); itr != blue.end(); itr++) {
        auto r = red.find(itr->first);
        maximum = max(maximum, r != red.end() ? itr->second - r->second : itr->second);
    }

    cout << maximum << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int a[100005], pos[100005];
int main(){

    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    multiset<int> ms;
    ms.insert(0); ms.insert(0);
    ms.insert(n+1); ms.insert(n+1);
    long long res = 0;
    
    for(int i = n; i >= 1; i--){
        ms.insert(pos[i]);
        auto it = ms.find(pos[i]);
        
        --it;
        int esq1 = *it;
        --it;
        int esq2 = *it;
        
        ++it; ++it; ++it;
        int dir1 = *it;
        it++;
        int dir2 = *it;
        
        res += 1LL*i*(esq1 - esq2)*(dir1 - pos[i]);
        res += 1LL*i*(pos[i] - esq1)*(dir2 - dir1);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<cstdio>
using namespace std;
const int N=25;
const int MOD=998244353;
int n,m;
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long fac[N],inv[N];
long long Pw[N];
void init(int n=20)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	Pw[0]=1;
	for(int i=1;i<=n;i++)
		Pw[i]=Pw[i-1]*2%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int r[N],c[N];
char s[N][N];
long long row[N][N][3],col[N][N][3];
int main()
{
	init();
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%s",s[i]);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			 if(s[i][j]=='.') r[i]|=1<<j,c[j]|=1<<i;
	for(int j=1;j<=m;j++)
		col[n][j][2]=C(m,j)*Pw[m-j]%MOD;
	long long ans=Pw[m];
	for(int i=n;i>=1;i--)
		for(int j=m;j>=1;j--)
		{
			col[i][j][0]=(col[i][j][1]+col[i][j][2])%MOD;
			for(int k=1;k<i;k++)
			{
				int d=i-k;
				row[k][j][1]=(row[k][j][1]+C(i,d)*(col[i][j][2]*2+col[i][j][1])%MOD)%MOD;
				row[k][j][2]=(row[k][j][2]+C(i,d)*(Pw[d]-2)%MOD*col[i][j][2]%MOD)%MOD;
			}
			ans=(ans+col[i][j][2]*(Pw[i]-2)%MOD)%MOD;
			row[i][j][0]=(row[i][j][1]+row[i][j][2])%MOD;
			for(int k=1;k<j;k++)
			{
				int d=j-k;
				col[i][k][1]=(col[i][k][1]+C(j,d)*(row[i][j][2]*2+row[i][j][1])%MOD)%MOD;
				col[i][k][2]=(col[i][k][2]+C(j,d)*(Pw[d]-2)%MOD*row[i][j][2]%MOD)%MOD;
			}
			ans=(ans+row[i][j][2]*(Pw[j]-2)%MOD)%MOD;
		}
	for(int i=1;i<(1<<n);i++)
		for(int j=1;j<(1<<m);j++)
		{
			bool flag=true;
			for(int k=0;k<n;k++)
				if(i&(1<<k))
				{
					int w=r[k]&j;
					if(w==j||w==0)
					{
						flag=false;
						break;
					}
				}
			if(!flag) continue;
			for(int k=0;k<m;k++)
				if(j&(1<<k))
				{
					int w=c[k]&i;
					if(w==i||w==0)
					{
						flag=false;
						break;
					}
				}
			if(!flag) continue;
			int x=__builtin_popcount(i),y=__builtin_popcount(j);
			ans=(ans+(row[x][y][0]+col[x][y][0])%MOD*ksm(C(n,x),MOD-2)%MOD*ksm(C(m,y),MOD-2)%MOD)%MOD;
		}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3736
#include <iostream>
using namespace std;
int n,k,d,ans,x,a[110];
int main(void)
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>d;
        while(d--)
        {
            cin>>x;
            a[x]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!a[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
const int maxn=112345;
typedef pair<int,int> pii;
int n,m,l,r,x,d[maxn],vis[maxn];
vector<pii> G[maxn];
bool dfs(int u,int dep) {
    vis[u]=1;
    d[u]=dep;
    for (int i=0;i<(int)G[u].size();++i) {
        int v=G[u][i].first,w=G[u][i].second;
        if (vis[v]&&d[u]+w!=d[v]) return false;
        if (!vis[v]&&!dfs(v,dep+w)) return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;++i) {
        scanf("%d%d%d",&l,&r,&x);
        G[l].push_back(pii(r,x));
        G[r].push_back(pii(l,-x));
    }
    for (int i=1;i<=n;++i) if (!vis[i]&&!dfs(i,0))
        return 0*puts("No");
    return 0*puts("Yes");
}


Measured memory_bytes: 16988
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int phi(int x) {
    int ret = x;
    for (int i = 2; i * i <= x; i++) {
        bool flg = false;
        while (x % i == 0) {
            flg = true;
            x /= i;
        }
        if (flg) {
        ret /= i;
        ret *= i-1;
        }
    }
    if (x != 1) { ret /= x; ret *= x-1; }
    return ret;
}

int main() {
    int n; cin >> n;
    cout << phi(n) << endl;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int dp[100][2010];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    vector<int>b;
    for (int i = 0; i < n; i++)
    {
        b.push_back(a[i]);
        for (int j = 0; j < n; j++)
        {
            if(a[i+j+1]!=a[i]){
                i+=j;
                break;
            }
        }
        
    }
      
    
  
    vector<int>c;
        c.push_back(INF);
   
    for (int i = 0; i < b.size(); i++)
    {
        c.push_back(b[i]);
    }
    if(b.back() > b[b.size()-2]) c.push_back(0);
    else c.push_back(INF);
    
   
    if(b.size()==1){
        cout<<1000<<endl;
        return 0;
    }  
    int pos=1000;
    int kab=0;
    int ans=0;
    //show(c);
    for (int i = 0; i < c.size()-1; i++)
    {
       if(c[i-1] < c[i] && c[i] > c[i+1]){
           pos+=c[i]*kab;
           kab=0;
       }
       else if (c[i-1] > c[i] && c[i] < c[i+1]){
           kab+=pos/c[i];
           pos%=c[i];
       }
       //cerr<<pos<<endl;
       chmax(ans,pos);
    }
    cout<<ans<<endl;
        
    
  
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define sc(x) scanf("%d", &x)
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ALL(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define ABS(x) ((x)>=0?(x):(-(x)))
#define fastio ios::sync_with_stdio(0),cin.tie(0)
template<class T>T gcd(T a, T b){return b?gcd(b, a%b):a;}
const int maxn = 1e5+10;
int flt[maxn];

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    bool flg = 1;
    set<int> st;
    for(int i = 0; i < n; i++){
        if(!flt[(int)s[i]]){
            if(st.count(t[i])){
                flg = 0;
                break;
            }
            else{
                flt[(int)s[i]] = t[i];
                st.insert(t[i]);
            }   
        }
        else if(flt[(int)s[i]] != t[i]){
            flg = 0;
            break;
        }
    }
    if(flg)puts("Yes");
    else puts("No");
    return 0;
}



Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch Folia | diff Folia.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address Folia.cpp && ./a.out

/*

 5/30/2020

 5:07-6:23 WA
 7:00 give up

 */

const int MAX_N=1e6+1;
LL A[MAX_N];
int N;

void nope() {
  cout<<-1<<endl;
  exit(0);
}
void solve() {
  if(N==0) {
    if(A[0]==1) cout<<1<<endl;
    else nope();
    return;
  }
  vector<LL> B(N+1),PLB(N+1),RB(N+1);
  B[N]=A[N];
  for(int i=N-1; i>=0; --i) {
    B[i]=A[i]+(B[i+1]+1)/2;
    PLB[i]=(B[i+1]+1)/2;
    RB[i]=A[i]+i<N?RB[i+1]:0;
    if(i<60&&B[i]>(1LL<<i)) nope();
  }
  vector<LL> res(N+1);
  res[N]=A[N];
  for(int i=N-1; i>=0; --i) {
    res[i]=A[i]+res[i+1];
    if(i<60) {
      res[i]=min({res[i],1LL<<i});
    }
  }
  FORE(i,1,N) {
    res[i]=min({res[i],2LL*(res[i-1]-A[i-1])});
    //dump(i,res[i],PLB[i],2LL*(res[i-1]-A[i-1]));
    assert(res[i]-A[i]>=PLB[i]);
  }

  //dumpc(res);
  REP(i,N) {
    //dump(i,res[i+1],(res[i]-A[i])*2);
    assert(res[i]-A[i]<=res[i+1]&&res[i+1]<=(res[i]-A[i])*2);
  }
  LL ans=accumulate(ALL(res),0LL);
  cout<<ans<<endl;
}

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

  cin>>N;
  REP(i,N+1) cin>>A[i];
  solve();

  return 0;
}


Measured memory_bytes: 7160
#include<bits/stdc++.h>
#define For(a,b,c) for(register int a=b;a<=c;++a)
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n;
char s[12];
int c[12];
map<string,long long>mp;
long long ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(int j=1;j<=10;j++){
			c[j]=s[j]-'a';
		}
		sort(c+1,c+10+1);
		string p="";
		for(int j=1;j<=10;j++){
			p+=(c[j]+'a');
		}
		ans+=mp[p];mp[p]++;
	}
	cout<<ans;	
}

Measured memory_bytes: 12800
N = int(input())
a_list = []
b_list = []
c_list = []
for i in range(N):
    a,b,c = map(int,input().split())
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    
abc_list = [a_list,b_list,c_list]

three_hpnses = [[0 for _ in range(N+1)] for _ in range(3)]

for i in range(N):
    for pre_play in range(3):
        now_hpns = three_hpnses[pre_play][i]
        for j in range(1,3):
            next_play = (pre_play+j)%3
            next_hpns = now_hpns + abc_list[next_play][i]
            three_hpnses[next_play][i+1] = max(three_hpnses[next_play][i+1], next_hpns)

print(max([hpnses[-1] for hpnses in three_hpnses]))

Measured memory_bytes: 82520
#include <iostream>
#include <string>
using namespace std;
#define MAX_N 100
typedef long long ll;

int n, k;
string s;

void solve()
{
    int l_cnt = 0;
    int r_cnt = 0;
    char pre = 'c';
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == pre)
        {
            ans++;
        }
        pre = s[i];
    }

    ans += 2 * k;
    ans = min(ans, n - 1);
    cout << ans;
}

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

    cin >> s;

    solve();
}


Measured memory_bytes: 512
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
#print(factorization(N))

ans = factorization(N)
#print(ans)
if ans == [[1,1]]:
    print(0)
else:
    sum = 0
    for i in range(len(ans)):
        n = 1
        while ans[i][1] >= n:
            ans[i][1] -= n
            sum += 1
            n += 1
    print(sum)

Measured memory_bytes: 9492
#include <iostream>
using namespace std;
 
int main(){
  while(1){
    int n,m;
    cin >> n >> m;
 
    if(n==0 && m==0)
      break;
 
    int a[1000];
    for(int i=0;i<n;i++){
      cin >> a[i];
    }
 
    int max=-1;
 
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        int p=a[i]+a[j];
 
        if(max<p && p<=m)
          max=p;
      }
    }
 
    if(max==-1){
      cout << "NONE" << endl;
    }else {
      cout << max << endl;
    }
  }
 
  return 0;
}


Measured memory_bytes: 3096