akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, k;
int a[N];
ll suff[N];


int main () {
	SpeedForce;
	
	cin >> n;
	for (int i = 0; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = n; ~i; --i) {
		suff[i] = suff[i+1] + a[i];
	}

	ll cnt = 1;
	ll ans = 1;
	if(a[0]>1) {
		cout <<"-1\n";
		return 0;
	}
	if(a[0])--cnt;

	for (int i = 1; i <= n; ++i) {
		cnt *= 2;
	    if(a[i] > cnt) {
			cout <<"-1\n";
			return 0;
		}
		cnt=min(cnt, suff[i]);
		ans += cnt;
		cnt -= a[i];
	}

	cout << ans << '\n';

	return Accepted;
}

// B...a

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

ll pot(ll a, ll b)
{
    if (b == 1)
        return a;
    if (b % 2 == 1)
        return a * pot(a, b - 1) % MOD;
    ll x = pot(a, b / 2);
    return x * x % MOD;
}

ll inv(ll a)
{
    return pot(a, MOD - 2);
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    string nap;
    cin >> n >> nap;
    int l = nap.size();
    if (n < l)
    {
        cout << "0";
        return 0;
    }
    vector< vector<ll> > dp(n + 1, vector<ll>(n + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 0; j < i + 1; ++j)
        {
            if (j - 1 >= 0)
                dp[i][j] = (dp[i][j] + 2 * dp[i - 1][j - 1]) % MOD;
            if (j + 1 <= n && j + 1 <= i - 1)
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
            if (j == 0)
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
        }
    }
    ll odp = dp[n][l] * inv(pot(2, l)) % MOD;
    cout << odp;
    return 0;
}


Measured memory_bytes: 195840
n = int(input())
a_lis = list(map(int,input().split()))
b_lis = list(map(int,input().split()))

ans = 0

for i in range(n):
	if b_lis[i] <= a_lis[i]:
		ans += b_lis[i]
	else:                                     
		ans += a_lis[i]
		b_lis[i] -= a_lis[i]
		if b_lis[i] <= a_lis[i+1]:
			ans += b_lis[i]
			a_lis[i+1] -= b_lis[i]
		else:
			ans +=  a_lis[i+1]
			a_lis[i+1] = 0
print(ans)

Measured memory_bytes: 18624
#include <vector>
#include <iostream>
#include <cstdlib>

static const int INF = 1001001001;

using namespace std;

int main()
{
	int x;
	cin >> x;
	if (x < 1200) {
		cout << "ABC" << endl;
	} else {
		cout << "ARC" << endl;
	}

	return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int main() {
  map<string, int> m;
  vector<string> v{"AC", "WA", "TLE", "RE"};
  int N; cin >> N;
  while (N--) {
    string s; cin >> s; m[s]++;
  }
  for (auto s : v) {
    cout << s << " x " << m[s] << endl;
  }
}
  
    

Measured memory_bytes: 3620
use std::fmt::Debug;
use std::str::FromStr;

#[allow(dead_code)]
#[allow(deprecated)]
fn read_line_from_stdin() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).unwrap();
    buffer.trim_right().to_owned()
}

#[allow(dead_code)]
#[allow(deprecated)]
fn parse_line_to_single<T>() -> T
where
    T: FromStr,
    T::Err: Debug,
{
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).unwrap();
    T::from_str(buffer.trim_right()).unwrap()
}

#[allow(dead_code)]
#[allow(deprecated)]
fn parse_line_to_multiple<T>() -> Vec<T>
where
    T: FromStr,
    T::Err: Debug,
{
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).unwrap();
    buffer
        .trim_right()
        .split_whitespace()
        .flat_map(|s| T::from_str(s))
        .collect()
}

#[allow(unused_macros)]
macro_rules! parse_line {
    [$( $x:tt : $t:ty ),+] => {
        //declare variables
        $( let $x: $t; )+
        {
            use std::str::FromStr;
            // read
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).unwrap();
            #[allow(deprecated)]
            let mut splits = buf.trim_right().split_whitespace();
            // assign each variable
            $(
                $x = splits.next().and_then(|s| <$t>::from_str(s).ok()).unwrap();
            )+
            // all strs should be used for assignment
            assert!(splits.next().is_none());
        }
    };
}

use std::collections::HashSet;

struct Fact {
    base: u64,
    power: u64,
}

fn factorization(n: u64) -> Vec<Fact> {
    let mut arr = vec![];
    let mut temp = n;
    for i in 2..(n as f64).sqrt() as u64 + 1 {
        if temp % i == 0 {
            let mut cnt = 0;
            while temp % i == 0 {
                cnt += 1;
                temp /= i;
            }
            arr.push(Fact {
                base: i,
                power: cnt,
            });
        }
    }

    if temp != 1 {
        arr.push(Fact {
            base: temp,
            power: 1,
        });
    }

    arr
}

fn main() {
    let n = parse_line_to_single::<u64>();

    if n == 1 {
        println!("0",);
        return;
    }

    let facts = factorization(n);

    let mut operation_count = 0;

    for Fact { base: _, mut power } in facts.into_iter() {
        let mut temp_operation_count = 0;
        let mut current_power = 1;

        while power >= current_power {
            power -= current_power;
            current_power += 1;
            temp_operation_count += 1;
        }

        operation_count += temp_operation_count;
    }

    println!("{}", operation_count);
}


Measured memory_bytes: 2164
import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
    Map<String, Integer> week = new HashMap<>();
    week.put("SUN", 1);
    week.put("MON", 2);
    week.put("TUE", 3);
    week.put("WED", 4);
    week.put("THU", 5);
    week.put("FRI", 6);
    week.put("SAT", 7);
    
    int temp = week.get(br.readLine());
    temp++;
    int result = 1;
    while (temp%7 != 1){
      temp++;
      result++;
    }
    System.out.println(result);
  }
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

using pv = pair<P,vector<int>>;
vector<int> graph[1005];

int main(){
    int n,m;
    cin >> n >> m;
    vector<P> edge(m);
    rep(i,m){
        cin >> edge[i].first >> edge[i].second;
        --edge[i].first;--edge[i].second;
        graph[edge[i].first].push_back(edge[i].second);
    }
    int id = -1;
    int mn = INF;
    vector<int> ans;
    rep(i,m){
        vector<bool> seen(n,false);
        queue<pv> q;
        q.push(pv(P(edge[i].second,0),{}));
        while(!q.empty()){
            int now = q.front().first.first;
            int c = q.front().first.second;
            vector<int> way = q.front().second;
            q.pop();
            if(now==edge[i].first){
                if(c < mn){
                    id = i;
                    mn = c;
                    way.push_back(now);
                    ans = way;
                    break;
                }else{
                    break;
                }
            }
            if(seen[now]) continue;
            seen[now] = true;
            way.push_back(now);
            for(int j:graph[now]){
                if(seen[j]) continue;
                q.push(pv(P(j,c+1),way));
            }
        }
    }
    if(mn==INF){
        cout << -1 << endl;
    }else{
        cout << (int)ans.size() << endl;
        rep(i,ans.size()) cout << ans[i]+1 << endl;
    }
    return 0;
}

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

/* clang-format off */
// #define int long long
struct Fast {Fast() {cin.tie(0); ios::sync_with_stdio(false);}} fast;

#define reps(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n+1)
#define deps(i, a, n) for (int i = (a); i >= (int)(n); --i)
#define dep(i, n) deps(i, n, 0)
#define each(i, n) for (auto&& i : n)

template <typename T> inline size_t maxElement(T beginIt, T endIt) { return max_element(beginIt, endIt); }
template <typename T> inline size_t minElement(T beginIt, T endIt) { return min_element(beginIt, endIt); }
template <typename T> inline size_t maxIndex(T beginIt, T endIt) { return distance(beginIt, *max_element(beginIt, endIt)); }
template <typename T> inline size_t minIndex(T beginIt, T endIt) { return distance(beginIt, *min_element(beginIt, endIt)); }
template <typename T> inline int sum(T beginIt, T endIt) { return accumulate(beginIt, endIt, 0); }
template <typename T> inline int mean(T beginIt, T endIt) { return sum(beginIt, endIt) / distance(beginIt, endIt); }
template <typename T> inline void debug(T x) { cerr << x << " " << "(L:" << __LINE__ << ")" << endl; }
/* clang-format on */

signed main(void) {
  /* */
  int num;
  num = 0; // counter
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int N;
  // array<int, 200000> A;
  string S;
  /* */

  int w;
  cin >> S;
  cin >> w;

  for (unsigned int i = 0; i < S.size(); i++) {
    if (i % w == 0) cout << S[i];
  }

  cout << endl;

  // cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 INF 999999999
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;



int main(){
  ll A,B,K,T,O;
  cin >> A >> B >> K;
  T = max((ll)0,A-K);
  O = max((ll)0,B-(K-(A-T)));
  cout << T << " " << O;
  return 0;
}

Measured memory_bytes: 256
import sys


def solve(N: int, S: "List[str]", P: "List[int]"):
    data = list(zip(S, map(lambda x: -x, P), range(1, N + 1)))
    data.sort()
    return "\n".join(str(t[2]) for t in data)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [str()] * (N)  # type: "List[str]"
    P = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = next(tokens)
        P[i] = int(next(tokens))
    ans = solve(N, S, P)
    if ans is not None:
        print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (int i = (int)(x); i < (int)(n); i++)
#define repfr(i, x, n) for (int i = (int)(x)-1; i >= (int)(n); i--)
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> inline void in(T &a) { cin >> a; }
template <class T, class U> inline void in(T &a, U &b) { cin >> a >> b; }
template <class T, class U, class V> inline void in(T &a, U &b, V &c) {
  cin >> a >> b >> c;
}
template <class T> inline void out(T a) { std::cout << a << endl; }
template <class T, class U> inline void out(T a, U b) {
  cout << a << ' ' << b << endl;
}
template <class T, class U, class V> inline void out(T a, U b, V c) {
  cout << a << ' ' << b << ' ' << c << endl;
}
#define inf 1e9
using ll = int64_t;

void Main() {
  int n;
  cin >> n;
  std::vector<ll> a(n), b(n), c(n);
  for (auto &x : a) {
    in(x);
  }
  for (auto &x : b) {
    in(x);
  }
  for (auto &x : c) {
    in(x);
  }

  sort(all(a));
  sort(all(c));

  ll ans = 0;

  for (auto &x : b) {
    auto itra = lower_bound(a.begin(), a.end(), x);
    auto itrc = upper_bound(c.begin(), c.end(), x);
    ans += (itra - a.begin()) * (c.end() - itrc);
  }

  out(ans);

  return;
}

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


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

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main(){

    int N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    int ans = A[0];
    for(int i = 1; i < N; i++){
        ans = gcd(ans, A[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

s = input()

print("ABC" if s=="ARC" else "ARC")


Measured memory_bytes: 67612
n, s = map(int, input().split())

for x in range(n+1):
    for y in range(n+1-x):
        z = n-(x+y)
        if (10000*x) + (5000*y) + (1000*z) == s:
            print(x, y, z)
            exit()

print(-1, -1, -1)

Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll t,m,sum,cnt,sum2;
double ave;
char ch;
int main(){
	sum=sum2=cnt=0;
	while(cin>>t>>ch>>m){
		//cin>>t>>m;
		//if(t==0)break;
		sum+=t*m;
		cnt++;
		sum2+=m;
	}
	//ave=(double)sum2/cnt;
	cout<<sum<<endl;
	cout<<(int)(sum2/(double)cnt+0.5)<<endl;
	//printf("%.0f\n",ave);
	//cin>>t;
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<math.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define N (1000000000+7)
#define INF (ll)1e16
typedef long long ll;

int main(void){
    int a[5];
    int k;
    for(int i=0;i<5;i++)cin>>a[i];
    cin>>k;
    for(int i=0;i<4;i++){
        for(int j=i+1;j<5;j++){
            if(i==j)continue;
            if(a[j]-a[i]>k){
                cout<<":("<<endl;
                return 0;
            }
        }
    }
    cout<<"Yay!"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll N;
  cin>>N;
  ll ans = 1;
  for(ll i=1;i<=N;++i) ans = ans*i%mod;
  cout<<ans<<endl;
}



Measured memory_bytes: 3548
s = int(input())
mod = pow(10, 9)+7
def calc(s):
    if s<=2:
        return 0
    if 3<=s<6:
        return 1
    if s==6:
        return 2
    if s==7:
        return 3
    if s==8:
        return 4
    else:
        s1 = 1
        s2 = 2
        s3 = 3
        s4 = 4
        for _ in range(s-8):
            tmp = s1
            s1 = s2%mod
            s2 = s3%mod
            s3 = s4%mod
            s4 = (tmp+s1+s2)%mod
        return s4
print(calc(s))

Measured memory_bytes: 63160
#include<iostream>
#include<utility>
#include<tuple>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<algorithm>

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FUNCTION__ << endl;
#define int long long

const long long MAXN = 1e6;
const long long MOD = 1e9+7;
const long long INF = __LONG_LONG_MAX__ / 2;

using namespace std;

int hoge[MAXN];

signed main(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a+3);
    cout << a[0]+a[1];;
    return 0;
}


Measured memory_bytes: 256
w = gets.chomp.chars.sort!
if w.size % 2 != 0
  puts "No"
else
  i = 0
  while i < w.size
    if w[i] != w[i+1]
      break
    end
    i += 2
  end
  if i == w.size
    puts "Yes"
  else
    puts "No"
  end
end

Measured memory_bytes: 14336
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
int main(){
  ll n;
  cin >>n;
  ll a[n];
  for(ll i=0;i<n;i++) cin >> a[i];
  int ans=0;int c=1;
  sort(a,a+n);
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]){
      c++;
      if(i==n-2){
        if(c%2==1) ans++;
      }
    }
    else{
      if(c%2==1) ans++;
      if(i==n-2) ans++;
      c=1;
    }
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <cstdlib>
#include <deque>
#include <stack>

using namespace std;
const long long P = 1000000007;
const long long INF = 1LL << 60;

int main() {
  long long x,y;
  cin >> x >> y;
  int a[2];
  int b[2];
  a[0] = x;
  a[1] = -1*x;
  b[0] = y;
  b[1] = -1*y;
  long long mn = INF;
  long long ans = 0;
  for(int i = 0; i <= 1; i++) {
    for(int j = 0; j <= 1; j++) {
      long long dist = b[j]-a[i];
      if(mn > dist && dist >= 0) {
        ans = i+j+dist;
        mn = dist;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    INF = int(1e12)
    G = [[0 for i in range(101)] for j in range(101)];

    v, e = map(int, raw_input().split())

    for i in range(v):
        for j in range(v):
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = INF

    for i in range(e):
        s, t, d = map(int, raw_input().split())
        G[s][t] = d

    for k in range(v):
        for i in range(v):
            for j in range(v):
                if G[i][k] != INF and G[k][j] != INF:
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    for i in range(v):
        if G[i][i] < 0:
            print "NEGATIVE CYCLE"
            return 0

    for i in range(v):
        ans = []

        for j in range(v):
            if G[i][j] == INF:
                ans.append("INF")
            else:
                ans.append(G[i][j])

        print " ".join(map(str, ans))

main()

Measured memory_bytes: 6968
/*author: hyperion_1724
  date: 
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	

	int N,K;
	cin>>N>>K;
	string S;
	cin>>S;
	int ans=0;
	bool q=false;
	vector<pair<int,int>> A;
	pair<int,int> X;
	for (int i = 0; i < N; ++i)
	{
		if(S[i]=='0' && q==false)
		{
			X.first=i;
			q=true;
		}
		if(S[i]=='1' && q==true)
		{
			X.second=i-1;
			q=false;
			A.push_back(X);
		}
	}	
	if(q)
	{
		X.second=N-1;
		A.push_back(X);
		q=false;
	}
	if(A.size()<=K)
	{
		ans=N;
	}
	else
	{
		int p=0;
		for (int i = 0; i < A.size()-K; ++i)
		{
			int x=A[i+K].first-p;
			if(x>ans)
			{
				ans=x;
			}
			p=A[i].second+1;
		}
		int z=N-1-A[A.size()-K-1].second;
		if(z>ans)
		{
			ans=z;
		}
	}
	cout<<ans<<endl;
	

	return 0;
}

Measured memory_bytes: 1020
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def next_mul(x,y):
    if x%y == 0:
        return x
    else:
        return x+y-x%y

N = I()
T,A = LIR(N,2)

t = T[0]
a = A[0]
for i in range(1,N):
    an = next_mul(a,A[i])
    tn = an*T[i]//A[i]
    if tn >= t:
        t = tn
        a = an
    else:
        t = next_mul(t,T[i])
        a = t*A[i]//T[i]
        
print(t+a)

Measured memory_bytes: 38896
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <thread>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>



int main() {
	ll n;
	string s;
	cin >> n >> s;
	REP(i, s.size()) {
		ll now = s[i] - 'A';
		now = (now + n) % 26;
		char a = 'A' + now;
		cout << a;
	}
	cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 59);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------

// function -------------------------------------------

// main -----------------------------------------------

int main() {
    ll n;
    cin >> n;
    char a[4] = {'A', 'W', 'T', 'R'};
    ll cnt[4] = {};
    REP(i, n){
        string s;
        cin >> s;
        REP(j, 4){
            if(s[0] == a[j]) {
                cnt[j] ++;
            }
        }
    }
    cout << "AC x " << cnt[0] << endl;
    cout << "WA x " << cnt[1] << endl;
    cout << "TLE x " << cnt[2] << endl;
    cout << "RE x " << cnt[3] << endl;

    return 0;
}

Measured memory_bytes: 3588
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    H = LI()

    res = 0
    for i in range(n)[::-1]:
        for j in range(i):
            if H[i] < H[j]:
                break
        else:
            res += 1

    return res


print(main())


Measured memory_bytes: 3064
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	string S,Sb="",Se="";
	ll Q;
	cin >> S >> Q;
	ll q, qk = 0;
	ll F;
	string C;
	rep(i, Q) {
		
		cin >> q;
		if (q == 1) {
			qk++;
		}
		else {
			
			cin >> F >> C;
			if (F==1&&qk%2==0) {
				Sb = C + Sb;
			}
			else if (F == 1 && qk % 2 != 0) {
				Se = Se + C;
			}
			else if(F == 2 && qk % 2 != 0) {
			Sb = C + Sb;
			}
			else {
				Se= Se + C;
			}
		}
	}
	
	if (qk % 2 != 0) {
		
		reverse(S.begin(), S.end());
		reverse(Sb.begin(), Sb.end());
		reverse(Se.begin(), Se.end());
		cout << Se + S + Sb << endl;
	}
	else {
		cout << Sb + S + Se << endl;
	}
	
}


Measured memory_bytes: 1464
#include <bits/stdc++.h>
 
using namespace std;
 
#define fast_cin ios_base::sync_with_stdio(false)
 
typedef long long ll;

int main()
{
	//freopen("input.txt", "r", stdin); //<---------Remove Before Submit
	fast_cin;
	int n; cin >> n;
	int cnt4 = 0,cnt2 = 0,cnt1 = 0;
	for (int i = 0; i < n; ++i)
	{
		ll a; cin >> a;
		if (a % 2)
		{
			cnt1++;		
		}
		
		else if (a % 4 == 0)
		{
			cnt4++;
		}
		else {
			cnt2++;
		}
	}
	if (cnt2 == 0)
	{
		if (cnt4 >= cnt1 - 1)
		{
			cout << "Yes";
		}
		else
			cout << "No";
	}
	else{
		if (cnt4 >= cnt1)
		{
			cout << "Yes";
		}
		else
			cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int l,cnt,gcount;
int ary[1000000];
int n;
int G[100];

void insertsort(int ary[],int n,int g){
  for(int i=g;i<n;i++){
    int v=ary[i];
    int j=i-g;
    while(j>=0 && ary[j]>v){
      ary[j+g]=ary[j];
      j-=g;
      cnt++;
    }
    ary[j+g]=v;
  }
}

void shellsort(int ary[],int n){
  int i,h=1;
  gcount=0;
  while(1){
    if(h>n)break;
    G[gcount]=h;
    h=3*h+1;
    gcount++;
  }
  for(i=gcount-1;i>=0;i--){
    insertsort(ary,n,G[i]);
  }
}

int main(){
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&ary[i]);
  }
  cnt=0;

  shellsort(ary,n);

  printf("%d\n",gcount);
  for(i=gcount-1;i>=0;i--){
    printf("%d",G[i]);
    if(i>0)printf(" ");
  }
  printf("\n");
  printf("%d\n",cnt);
  for(i=0;i<n;i++)printf("%d\n",ary[i]);
  return 0;
}



Measured memory_bytes: 5628
import sys

h, w, d = map(int, sys.stdin.readline().split())
a = [[int(x) for x in sys.stdin.readline().split()] for _ in range(h)]
q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2) 

def main():
    place = [None] * (h * w + 1)
    for i in range(h):
        for j in range(w):
            place[a[i][j]] = (i, j)
    
    cost = [None] * (h * w + 1)
    for x in range(1, 1+d):
        cost[x] = 0
        i, j = place[x]
        while x + d <= h * w:
            nex = x + d
            nex_i, nex_j = place[nex]
            cost[nex] = cost[x] + abs(nex_i - i) + abs(nex_j - j)
            x = nex
            i, j = nex_i, nex_j

    for l, r in lr:
        yield cost[r] - cost[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Measured memory_bytes: 33628
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <ostream& out = cout, class... T> void prints(T&&...){ }
template <ostream& out = cout, class... T> void printd(T&&...){ }
template <ostream& out = cout, class... T> void printb(T&&...){ }
template <ostream& out = cout, class... T> void printArr(T&&...){ }
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r, g, b;
    cin >> r >> g >> b;
    cout << ((r * 100 + g * 10 + b) % 4 == 0 ? "YES" : "NO") << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
#define mx 3003
typedef long long ll;
int dp[mx];
vector<int> g[mx];
void bfs(int n,int t)
{
    queue<pair<int,int>  > q;
    q.push({n,0});
    int vis[t+1]={};
    while(!q.empty())
    {
        pair<int,int> x=q.front();
        if(vis[x.ff])
        {
            q.pop();
            continue;
        }
        vis[x.ff]=1;
        dp[x.ss]+=1;
        q.pop();
        for(int i=0;i<g[x.ff].size();i++)
        {
            int v=g[x.ff][i];
            if(!vis[v])
            {
                q.push({v,x.ss+1});
            }
        }
    }
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,x,y;
cin>>n>>x>>y;
for(int i=1;i<=n-1;i++)
{
  g[i].pb(i+1);
  g[i+1].pb(i);
}
g[x].pb(y);
g[y].pb(x);
for(int i=1;i<=n;i++)
{
    bfs(i,n);
}
for(int i=1;i<=n-1;i++)
    cout<<dp[i]/2<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

typedef long long ll;

using namespace std;

int mypow(int a, int p){

    if(a == 0 && p == 0){
        return 1;
    }else if(p == 0){
        return 1;
    }else if(p == 1){
        return a;
    }else if(p % 2 == 0){
        ll tmp = mypow(a, p / 2);
        tmp = (tmp * tmp) % MODN;

        assert(tmp >= 0);
        return (int)tmp;
    }else{
        ll tmp = mypow(a, p / 2);
        tmp = (tmp * tmp) % MODN;
        tmp = (a * tmp) % MODN;
        assert(tmp >= 0);
        return (int)tmp;
    }
}

int main(){

    int x,y;
    cin >> x >> y;

    if((x + y) % 3 == 0){

        if(x < y){
            swap(x,y);
        }

        int tmpy = ((x + y) / 3 - (x - y)) / 2;
        int tmpx = (x + y) / 3 - tmpy;

        // (tmpx + tmpy)! / tmpx! * tmpy!になるはずなのでフェルマーの小定理を使って逆元を求めてどうのこうの

        ll ans = 1;

        for(int i = tmpx + tmpy; i > tmpx; i--){
            ans = (ans * i) % MODN;
        }

        ll tmp = 1;

        for(int i = 1; i <= tmpy; i++){
            tmp = (tmp * i) % MODN;
        }

        ans = (ans * mypow(tmp, MODN - 2)) % MODN;

        if(tmpx < 0 || tmpy < 0){
            ans = 0;
        }

        cout << ans << endl;

    }else{
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#define MAX_W 70
#define MAX_H 70
using namespace std;

string c[MAX_H];
char dp[MAX_H][MAX_W][MAX_H * MAX_W];

bool front_greater(char a[], char b[]) {
  if (strlen(a) > strlen(b)) return true;
  if (strlen(a) < strlen(b)) return false;
  
  for (int i = 0; i < strlen(a); i++) {
    int anum = a[i] - '0';
    int bnum = b[i] - '0';
    if (anum > bnum) return true;
    if (anum < bnum) return false;
  }
  return false;
}

void copy_push(char a[], char b[], char c) {
  int len = strlen(b);
  for (int i = 0; i < len; i++) {
    a[i] = b[i];
  }
  a[len] = c;
  a[len + 1] = '\0';
}

void search(int w, int h) {
  char secret[MAX_H * MAX_W];
  for (int i = 0; i < MAX_H * MAX_W; i++) {
    secret[i] = '\0';
  }
  
  strcpy(secret, dp[0][0]);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i == 0 && j == 0) continue;
      if (front_greater(dp[i][j], secret)) {
	strcpy(secret, dp[i][j]);
      }
    }
  }
  int len = strlen(secret);
  for (int i = 0; i < len; i++) {
    cout << secret[i];
  }
  cout << endl;
}

void set_number(char a[]) {
  while (a[0] == '0') {
    int len = strlen(a);
    for (int i = 1; i < len; i++) {
      a[i - 1] = a[i];
    }
    a[len - 1] = '\0';
  }
}

void init() {
  for (int i = 0; i < MAX_H; i++) {
    c[i].erase();
  }
  for (int i = 0; i < MAX_H; i++) {
    for (int j = 0; j < MAX_W; j++) {
      for (int k = 0; k < MAX_H * MAX_W; k++) {
	dp[i][j][k] = '\0';
      }
    }
  }
}

int main() {
  while (true) {
    int w, h;
    cin >> w >> h;
    if (w == 0 && h == 0) return 0;

    init();

    for (int i = 0; i < h; i++) {
      cin >> c[i];
    }

    if ('1' <= c[0][0] && c[0][0] <= '9') dp[0][0][0] = c[0][0];
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
	if ('0' <= c[i][j] && c[i][j] <= '9') {
	  if (i == 0) {
	    copy_push(dp[i][j], dp[i][j - 1], c[i][j]);
	    set_number(dp[i][j]);
	  } else if (j == 0) {
	    copy_push(dp[i][j], dp[i - 1][j], c[i][j]);
	    set_number(dp[i][j]);
	  } else {
	    if (front_greater(dp[i - 1][j], dp[i][j - 1])) {
	      copy_push(dp[i][j], dp[i - 1][j], c[i][j]);
	    } else {
	      copy_push(dp[i][j], dp[i][j - 1], c[i][j]);
	    }
	    set_number(dp[i][j]);
	  }
	}
      }
    }
    search(w, h);
  }
}

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

int main () {
    int a, b;
    cin >> a >>  b;
    
    if(a>b) {
        cout << "a > b" << endl;
    }else if(a<b){
        cout << "a < b" << endl;
    }else{
        cout <<  "a == b" << endl;  
    } 
    
    return 0;
}


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

int n,m;
static const int dx[4]={0,1,0,-1};
static const int dy[4]={1,0,-1,0};   

struct Robot{
  int x,y;
  int dire;
  void init(){
    x=1;
    y=1;
    dire=0;
  };
  void forward(int num){
    x+=dx[dire]*num;
    y+=dy[dire]*num;
    x=max(1,x); y=max(1,y);
    x=min(n,x); y=min(m,y);
  };
  void backward(int num){
    x-=dx[dire]*num;
    y-=dy[dire]*num;
    x=max(1,x); y=max(1,y);
    x=min(n,x); y=min(m,y);
  };
  void right(){
    dire++;
    if(dire==4) dire=0;
  };
  void left(){
    dire--;
    if(dire==-1) dire=3;
  };
};

int main(){
  string str;
  int kazu;
  Robot rb;
  while(1){
    cin>>n>>m;
    rb.init();
    if(n==0 && m==0) break;
    while(1){
      cin>>str;
      if(str=="FORWARD"){
	cin>>kazu;
	rb.forward(kazu);
      }else if(str=="BACKWARD"){
	cin>>kazu;
	rb.backward(kazu);
      }else if(str=="RIGHT"){
	rb.right();
      }else if(str=="LEFT"){
	rb.left();
      }else if(str=="STOP"){
	cout<<rb.x<<" "<<rb.y<<endl;
	break;
      }
    } 
  }
  return 0;
}

Measured memory_bytes: 1208
#16:50
n,m = map(int,input().split())
a = []
for _ in range(m):
  x,y = list(map(int,input().split()))
  x -= 1
  y -= 1
  a.append([x,y])
a.reverse()
scr = n * (n-1) // 2
pre = [-1 for _ in range(n)]
cnt = [1 for _ in range(n)]
ans = []
for i in range(m):
  ans.append(scr)
  X,Y = a[i]
  while pre[X] != -1:
    X = pre[X]
  while pre[Y] != -1:
    Y = pre[Y]
  x,y = min(X,Y), max(X,Y)
  if x != y:
    scr -= cnt[x] * cnt[y]
    pre[y] = x
    cnt[x] = cnt[x] + cnt[y]
  #print(pre)
  #print(cnt)
ans.reverse()
for z in ans:
  print(z)

Measured memory_bytes: 84440
#include <iostream> 
using namespace std;
void range(int s,int w,int korg)
{
   if((w-s)<=korg)
     cout<<"Yay!";
  else
    cout<<":(";
}
int main()
{
  int a,b,c,d,e,k;
  cin>>a>>b>>c>>d>>e>>k;
  range(a,e,k);
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <tuple>
using namespace std;
using ll=long long;
using R=double;

ll nC2(ll n){
	ll res = n*(n-1) / 2;
	return res;
}

int main(){
	int N;
	cin >> N;
	int P[N];
	for(int i = 0; i < N; i++){
		int x;
		cin >> x;
		P[x-1] = i;
	}

	int count = 1;
	int ans = 1;

	for(int i = 1; i < N; i ++){
		if(P[i] > P[i-1]){
			count++;
		}else{
			count = 1;
		}
		ans = max(ans, count);
	}

	cout << N-ans << endl;
	return 0;

}


Measured memory_bytes: 1024
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bitset>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef long long LL;

typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,n)  for(int i=0; i<(n); i++)

//constant
//--------------------------------------------
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const LL MOD = 1e9+7; 
//vector <vector<int>> x(20, vector<int> (20)), y(20,vector<int> (20));
/*int counter_1 (int x) {
    if(x == 0) return 0;
    return counter_1(x >> 1) + (x & 1);
}*/

//int Counter(int x)
/*int factorial(int n) {
    if (n > 0) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}*/
/*bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second > secondElof.second;
}*/


/*long nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1;
       if(r==0) return dp[n][r] = 1;
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r];
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}*/

int main(){
    int n, cnt, ans;
    cin >> n;
    VI a;
    LL sum=0;
    bool flg=false;
    REP(i, n){
        a.push_back(i+1);
        sum+=i+1;
        if(sum>=n){
            ans = i;
            if(sum>n){
                cnt = sum-n-1;
                flg=true;
            }
            break;
        }

    }
    if(n<=ans) cout << n << endl;
    else{
        LL s = a.size();
        if(flg){
            REP(i, s){
                if(i==cnt) continue;
                cout << a[i] << endl;
            }
        }else{
            REP(i,s){
                cout << a[i]  << endl;
            }
        }
    }



}


Measured memory_bytes: 384
"""
author : halo2halo
date : 16, Jan, 2020
"""

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

Y, M, D = readline().decode('utf8').split('/')
N = int(D) + int(M) * 100 + int(Y) * 10000
print('Heisei' if N <= 20190430 else 'TBD')


Measured memory_bytes: 12508
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

struct CumulativeSum{
    vector<int> data;
    CumulativeSum(int sz) : data(sz, 0) {};
    void add(int k, int x){
        data[k] += x;
    }
    void build(){
        for(int i = 1; i < data.size(); i++){
            data[i] += data[i - 1];
        }
    }
    int query(int k){
        if(k < 0) return 0;
        return (data[min(k, (int)data.size() - 1)]);
    }
    int query(int l, int r){
        return query(r - 1) - query(l - 1);
    }
};

int n;
int a[410];
int dp[410][410];
CumulativeSum cs(410);

int calc(int l, int r){
    if(l > r) return INF;
    if(l == r) return dp[l][r] = 0;
    if(dp[l][r] != -1) return dp[l][r];
    int res = INF;
    rep(k, l, r){
        int tmp = calc(l, k) + calc(k + 1, r) + cs.query(l, k + 1) + cs.query(k + 1, r + 1);
        res = min(res, tmp);
    }
    return dp[l][r] = res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    rep(i, 0, n){
        cin >> a[i];
        cs.add(i, a[i]);
    }
    cs.build();
    rep(i, 0, n + 1) rep(j, 0, n + 1) dp[i][j] = -1;
    cout << calc(0, n - 1) << endl;
}

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

int main() {
  int N;
  cin>>N;
  vector<int> vec(N),ans(N);
  for(int i=0;i<N;i++){
  	cin>>vec.at(i);
    int a;
    a=vec.at(i);
    ans.at(a-1)=i+1;
  }
  
  for(int i=0;i<N;i++){
  	cout<<ans.at(i)<<" ";
  }
  cout<<endl;
}

Measured memory_bytes: 1536
/*
author: Apoorv Singh
*/

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector <int> vi;
typedef vector <long long> vl;
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
#define ll long long
#define pb push_back   
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " " << (x) << endl;
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second

ll modulo = 1e9 + 7;

template <class X>

void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

ll fpow(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);   int n,k;
    cin >> n >> k;
    int arr[n];
    FOR(i,0,n)
    	cin >> arr[i];
    sort(arr, arr+n);
    int ans = 2e9;
    for (int i = 0; i+k-1 <= n-1; ++i)
    	ans = min(ans, arr[i+k-1]-arr[i]);
    cout << ans << endl;
    return 0;
}

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

int main()
{
    vector<int> x(5);

    for (int i = 0; i < 5; i++)
    {
        cin >> x[i];
    }

    int ans = 0;

    for (int i = 0; i < 5; i++)
    {
        if (x[i] == 0)
        {
            ans = i + 1;
            break;
        }
    }
    cout << ans << endl;
}

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

 int main() {
   int N;
   int A=0;
   int sum=0;
  cin>>N;
  vector<int> test(101);
  
  for(int i=0;i<N;i++){
    cin>>A;
    test.at(A)=1;
  }
    
  for(int i=0;i<101;i++){
    sum=sum+test.at(i);
  }
   cout<<sum<<endl;
 }

Measured memory_bytes: 3580
#include<stdio.h>
int main(){
  int a[20000];
  int b[20000];
  char op[20000];
  int i;
  int count=0;
  
  while(1){
    scanf("%d %c %d",&a[count],&op[count],&b[count]);
    if(op[count] == '?') break;
    count++;
  }

  for(i=0;i<count;i++){
    if(op[i] == '+'){
      printf("%d\n",a[i]+b[i]);
    }
    else if(op[i] == '-'){
      printf("%d\n",a[i]-b[i]);
    }
    else if(op[i] == '*'){
      printf("%d\n",a[i]*b[i]);
    }
    else printf("%d\n",a[i]/b[i]);
  }
  return 0;
}



Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll; ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);

int main(){
    ll n; cin>>n;
    vector<string>v(n);
    set<string>s;
    rep(i,n) {
        cin>>v[i];
        s.insert(v[i]);
    }
    sort(all(v));
    ll sum=s.size(), tmp=0;
    vector<ll>a(sum,1);
    vector<string>ans(sum);
    ans[0]=v[0];
    rep(i,n-1){
        if(v[i]==v[i+1]) a[tmp]++;
        else {
            tmp++;
            ans[tmp]=v[i+1];
        }
    }
    vector<ll>l(sum);
    rep(i,sum) l[i]=a[i];
    sort(all(l));
    reverse(all(l));
    ll ma=l[0];
    set<string>S;
    rep(i,sum){
        if(a[i]==ma){
            S.insert(ans[i]);
        }
    }
    for(auto val:S){
        cout<<val<<' ';
    }
    cout<<endl;
}

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

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

int main() {
    int x, y;
    cin >> x >> y;
    cout << GCD(x, y) << endl;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;  
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define Rep(i, a, b) for(ll i = a; i <= b; i++)
#define repr(i, a, b) for(ll i = b-1; i >= a; i--)
// #define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
// #define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
// const ll INF = 1LL << 60;
const ll INF = 100000000000;
#define pp pair<ll, pair<ll, ll>> 
// #define fi first
// #define se second
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
 
/*--------------------------------------------------------------------------------
 
--------------------------------------------------------------------------------*/


int main() {
    string s; cin >> s;
    ll n = sz(s);
    ll ans = n*(n-1)/2; // COM(n, 2)
    Vl c(26);
    rep(i, 0, n){
        c[s[i]-'a']++;
    }
    rep(i, 0, 26){
        ll m = c[i];
        if(m < 2) continue;
        ans -= m*(m-1)/2; // COM(m, 2)
    }
    co(ans+1);

    return 0;
}

Measured memory_bytes: 3648
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<functional>
using namespace std;
typedef long long LL;
inline LL read()
{
	LL kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
LL x,now;
int main()
{
	scanf("%lld",&x);
	now=100;
	for(int i=1;i<=1000000;++i)
	{
		now=now+now/100;
		if(now>=x)
		{
			printf("%d\n",i);
			return 0;
		}
	}
	
}

Measured memory_bytes: 3792