akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

// Inserted snippets: io, root
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
// End snippets

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  string s, t;
  read(s);
  for (char c : s) if (c != 'x') t += c;
  if (t != string(t.rbegin(), t.rend())) die(-1);
  if (t.empty()) die(0);

  //write(t);

  s = '$' + s + '$';
  int n = sz(s);
  int pl, pr;
  for (int i = 0, j = 0; i < n; i++) {
    bool sp = s[i] != 'x' && s[i] != '$';
    if (sp) j++;
    //if (sp) write("sp", i, s[i], j, sz(t) / 2, sz(t) / 2 + 1);
    if (sp && sz(t) % 2 == 1 && j == sz(t) / 2 + 1)
      pl = pr = i;
    if (sp && sz(t) % 2 == 0 && j == sz(t) / 2)
      pl = i;
    if (sp && sz(t) % 2 == 0 && j == sz(t) / 2 + 1)
      pr = i;
  }
  
  int ans = 0;
  rep(i, 0, sz(t) / 2 + 1) {
    int cl = 0, cr = 0;
    //write(pl, pr, s[pl], s[pr]);
    pl--, pr++;
    while (s[pl] == 'x') --pl, ++cl;
    while (s[pr] == 'x') ++pr, ++cr;
    ans += abs(cr - cl);
    //write(':', abs(cr - cl));
  }
  write(ans);
}


Measured memory_bytes: 3884
import sys
input = sys.stdin.readline

n = int(input())

plus = []
minus = []
for _ in range(n):
    min_s = 0
    ts = 0
    s = input().strip()
    for c in s:
        ts += 1 if c == '(' else -1
        min_s = min(ts, min_s)
    if ts >= 0:
        plus.append((-min_s, ts))
    else:
        minus.append((-(min_s - ts), -ts))

plus.sort()
minus.sort()

s1 = 0
for m, t in plus:
    if s1 - m < 0:
        print('No')
        exit()
    s1 += t

s2 = 0
for m, t in minus:
    if s2 - m < 0:
        print('No')
        exit()
    s2 += t

if s1 == s2:
    print('Yes')
else:
    print('No')


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

#define Inf (long long)(1e18)

int T,a,b,c,d;
long long n;
map<long long,long long>f;

long long F(long long n){
	if(f.count(n))return f[n];
	if(n<=1)return 1LL*n*d;
	long long val=Inf;
	if(Inf/n>d)val=1LL*n*d;
	int c2=n%2,c3=n%3,c5=n%5;
	if(!c2)val=min(val,F(n/2)+a);
	else val=min(val,min(F((n+2-c2)/2)+a+1LL*(2-c2)*d,F((n-c2)/2)+a+1LL*c2*d));
	if(!c3)val=min(val,F(n/3)+b);
	else val=min(val,min(F((n+3-c3)/3)+b+1LL*(3-c3)*d,F((n-c3)/3)+b+1LL*c3*d));
	if(!c5)val=min(val,F(n/5)+c);
	else val=min(val,min(F((n+5-c5)/5)+c+1LL*(5-c5)*d,F((n-c5)/5)+c+1LL*c5*d));
	return f[n]=val;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);
		f.clear();
		printf("%lld\n",F(n));
	}
	return 0;
}

Measured memory_bytes: 4516
import scala.io.StdIn.readLine

object Main extends App {
  def calc(op:String,x:Int,y:Int) = {
    op match {
      case "+" => x+y
      case "-" => x-y
      case "*" => x*y
    }
  }

  def revP(l:List[String],stack:List[Int]):Int =  {
    l match {
      case Nil => stack(0)
      case hd::tl =>
        val stack2 =
          if(hd.forall(_.isDigit)) hd.toInt::stack
          else {
            val x::y::ts = stack
            calc(hd,y,x)::ts
          }
        revP(tl,stack2)
    }
  }

  val l = readLine.split(" ").toList
  println(revP(l,Nil))

}

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

const ll mod=1000000007;

int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    ll sum=0;
    rep(i,n){
        cin>>a[i];
        sum+=(a[i]%mod);
        sum%=mod;
    }

    ll ans=0;
    rep(i,n-1){
        sum-=(a[i]%mod);
        if(sum<0)sum+=mod;
        ans+=(((a[i]%mod)*sum)%mod);
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4768
#include <iostream> 
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<queue>
#include<deque>
#include<iomanip>
#include<sstream>
#include<cmath>
#include<tuple>
#include<bitset>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define req(i,n) for(ll i = 1;i <=  n; i++)
#define rrep(i,n) for(ll i = n -1;i >= 0;i--)
#define ALL(obj) begin(obj), end(obj)
#define RALL(a) rbegin(a),rend(a)
typedef long long int ll;
typedef long double ld;
const ll INF = 1e18;
const double eps = 1e-8;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
    std::fill((T*)array, (T*)(array + N), val);
}ll n, m, s, t, r, Q, b, c; 
vector<ll> a,f,D;
const int MOD = 1e9 + 7;
bool ch(ll x) {
    ll sum = 0;
    rep(i, n) {
        sum += max(a[i] - x / f[i],0LL);
    }return sum <= m;
}
int main(void) {
    cin >> n >> m; a.resize(n); f.resize(n); D.resize(n);
    rep(i, n)  cin >> a[i];
    rep(i, n) cin >> f[i];
    sort(ALL(a)); sort(RALL(f));
    ll left = -1, right = 1e18;
    while (right - left > 1) {
        ll mid = (left + right) / 2;
        if (ch(mid)) right = mid;
        else left = mid;
    }cout << right << endl;
}

Measured memory_bytes: 4992
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        String[] lines = getStdin();
        String[] str = lines[0].split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        String[] a = lines[1].split(" ");
        int[] aa = new int[a.length];
        int plus = 0;
        
            for (int i = 0; i < m; i++){
                aa[i] = Integer.parseInt(a[i]);
            }
            for(int i = 0; i < m; i++){
                 plus = plus + aa[i];
            }
            if(n >= plus){
                System.out.println(n - plus);
            } else {
                System.out.println(-1);
            }
   }
  private static String[] getStdin() {
    Scanner scanner = new Scanner(System.in);
    ArrayList<String> lines = new ArrayList<>();
    while (scanner.hasNext()) {
      lines.add(scanner.nextLine());
    }
    return lines.toArray(new String[lines.size()]);
  }
}

Measured memory_bytes: 30564
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		sc.close();
		
		int ans = B;
		if(A<=5) {
			ans = 0;
		}else if(A<=12) {
			ans = ans / 2;
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 23252
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if (b >= a) 
    {
        for(int i = 0; i < b; i ++)
        {
            cout << a;
        }
    } else {
        for(int i = 0; i < a; i ++)
        {
            cout << b;
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import numpy as np


def main(A, B, V, W, T):
    if abs(B-A) <= T*(V-W):
        return "YES"
    return "NO"


A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())
print(main(A, B, V, W, T))


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

#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using pint = pair<int, int>;
using pstring = pair<int, string>;

vector<int> a(100);
int main() {
    ll ans = 0;
    ll N;
    cin >> N;
    for(ll i = 0; i < N; i++) {
        cin >> a.at(i);
    }
    for(ll j = 0; j < N; j += 2) {
        if(a.at(j) % 2 == 1) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
	int n, q;
	string s;


	cin >> n >> q;
	cin >> s;

	vector<int>a(n+1);
	
	for (int i = 1; i < n; i++)
		if (s[i-1]=='A'&&s[i]=='C')
			a[i + 1] = a[i] + 1;
		else
			a[i + 1] = a[i];

	for (int i = 0; i < q; i++){
		int l, r, ans = 0;
		cin >> l >> r;

		cout << a[r]-a[l] << endl;
	}

	return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>

#define N 100

void trace(int A[], int length, int index) {
  int i;
  for (i = 0; i < length -1; i++) {
    printf("%d ", A[i]);
  }
  printf("%d\n", A[i]);
  printf("%d\n", index);
}


int main() {
  int length, i, j, tmp, minj;
  int index = 0;
  int A[N];
  scanf("%d", &length);
  for (i = 0; i < length; i++) {
    scanf("%d", &A[i]);
  }
  for (i = 0; i < length; i++) {
    minj = i;
    for (j = i; j < length; j++) {
      if (A[j] < A[minj]) {
        minj = j;
      }
    }
      tmp = A[i];
      A[i] = A[minj];
      A[minj] = tmp;
      if (A[i] != A[minj]) {
        index++;
      }
      }
  trace(A, length, index);
  return 0;
}

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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

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

vector<int> v;
int dp[100005][2];
int n;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    const ll INF = 1e16;
    cin>>n;

    ll A[n];
    for (int i=0;i<n;++i) cin>>A[i];
    vector<vector<ll> > dp(n+1, vector<ll> (2, -INF));

    dp[0][0] = 0;
    for (int i=1;i<=n;++i){
        for (int j=0;j<2;++j){
            if (j==0){
                dp[i][j] = max(dp[i-1][0] + A[i-1], dp[i-1][1] - A[i-1]);
            }
            else {
                dp[i][j] = max(dp[i-1][0] - A[i-1], dp[i-1][1] + A[i-1]);
            }
        }
    }
    cout<<dp[n][0]<<endl;

    return 0;
}

Measured memory_bytes: 6528
#129
N=int(input())
w=list(map(int,input().split()))
s=[]
for i in range(N):
    s.append( abs(sum(w[-1-i:])-sum(w[:-1-i])) )
    if i==0:
        continue
    elif s[i]>s[i-1]:
        print(s[i-1])
        break
    

Measured memory_bytes: 3060
#include <iostream>

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


Measured memory_bytes: 3060
from collections import defaultdict
d = defaultdict(int)
import math
def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a
def calc(n):
    res = 0
    cnt = 1
    while True:
        if n - cnt < 0:
            return res
        n -= cnt
        res += 1
        cnt += 1
N = int(input())
for i in trial_division(N):
    if i != 1:
        d[i] += 1
ans = 0
for i in d.values():
    ans += calc(i)
print(ans)

Measured memory_bytes: 68048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 0;
    for(int i = 0; i < S.size(); i++) {
        string x = S.substr(0, i);
        string y = S.substr(i, S.size());
        set<char> st;
        int nowans = 0;
        for(int i = 0; i < x.size(); i++) st.insert(S[i]);
        for(int i = 0; i < y.size(); i++) {
            if(st.find(y[i]) != st.end()) {
                st.erase(y[i]);
                nowans++;
            }
        }
        chmax(ans, nowans);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;


void main() {
    int n;
    scan(n);
    auto s = readln.chomp;

    int e, w;

    foreach (i ; 0 .. n) {
        if (s[i] == 'E') e++;
    }

    int ans = 1<<30;

    foreach (i ; 0 .. n) {
        if (ans > e + w) {
            ans = e + w;
        }

        if (s[i] == 'E') e--;
        if (s[i] == 'W') w++;
    }

    ans = min(ans, e + w);

    writeln(ans);
}













































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

int main() {
	// your code goes here
	int n;
	cin>>n;
	string a[4]={"AC","WA","TLE","RE"};
	int count[4]={0,0,0,0};
	string input[n];
	for(int i=0;i<n;i++){
	    cin>>input[i];
	    if(input[i]=="AC"){
	        count[0]++;
	    }else if(input[i]=="WA"){
	        count[1]++;
	    }else if(input[i]=="TLE"){
	        count[2]++;
	    }else{
	        count[3]++;
	    }
	}
	for(int i=0;i<4;i++){
	    cout<<a[i]<<" x "<<count[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 6756
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}


fn main() {
    let line: Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();

    let n = line[0];
    let a = line[1] as u64;
    let b = line[2] as u64;

    let mut h = Vec::with_capacity(n);
    for i in 0..n {
        let v: u64 = read_line().trim().parse().unwrap();
        h.push(v);
    }

    h.sort();

    let mut l = 0;
    let mut r = 1_000_000_010;

    while r-l > 1 {
        let mid = (r + l)/2;
        let mut tmp = 0;
        let base = mid * b;
        for i in 0..n {
            if h[i] <= base {
                continue;
            }
            tmp += (h[i] - base + a - b - 1) / (a - b);
            if tmp > mid {
                break;
            }
        }
        if tmp <= mid {
            r = mid;
        } else {
            l = mid;
        }
    }
    println!("{}", r);
}


Measured memory_bytes: 4352
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

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

typedef long long ll;
const int MOD = 1000000007;

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  int cnt1 = 0, cnt4 = 0, cnt2 = 0;
  for(int i = 0; i < N; i++){
    cin >> a[i];
    if(a[i] % 2 == 1){
      cnt1++;
    }else if(a[i] % 4 == 0){
      cnt4++;
    }else{
      cnt2++;
    }
  }
  if(cnt1 <= cnt4){
    cout << "Yes" << endl;
  }else if(cnt2 == 0 && cnt1 - 1 == cnt4){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }
    ll ans = 1000;
    ll kabu = 0;
    ll left = 0;
    ll right = 1;
    vector<bool> B(N, false);
    while (right < N){
        if (A[left] == A[right]){
            right++;
        }
        else if (A[left] < A[right]){
            for (int i = left; i < right; i++){
                B[i] = true;
                left = right;
            }
        }
        else{
            for (int i = left; i < right; i++){
                B[i] = false;
                left = right;
            }
        }
    }
    rep(i,N){
        if (B[i]){
            ll kabu_sub = ans / A[i];
            ans -= kabu_sub * A[i];
            kabu += kabu_sub;
        }else{
            ans += kabu * A[i];
            kabu = 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int main(){
  //解説みました
  int n;
  cin >> n;
  vector<tuple<string,int,int>> list;
  repi(i,1,n+1){
    string s;
    int p;
    cin >> s >>p;
    p = -p;
    list.push_back(tie(s,p,i));
  }
  sort(list.begin(),list.end());
  rep(i,n){
    string s;
    int p;
    int id;
    tie(s,p,id) = list[i];
    cout << id << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    char n[4];
    int i;
    scanf("%s", n);
    for (i = 0; i < 3; ++i) {
        if (n[i] == '1') n[i] = '9';
        else if (n[i] == '9') n[i] = '1';
    }
    puts(n);
    return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
  int n; cin >> n;
  vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  int cur = 1;
  int result = 0;
  for (int i = 1; i <= n; ++i) {
    if (i == n || a[i] != a[i - 1]) {
      result += cur / 2;
      cur = 1;
    } else {
      cur++;
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
/**
*    author:  Dooloper
*    created: 06.06.2020 09:17:55
**/

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <functional>
#include <cassert>


using namespace std;
typedef unsigned long long ull;
typedef long long ll;

vector<pair<ll,int>> primeFactor(ll N){
    vector<pair<ll, int>> ret;
    ll target = N;

    for (ll i = 2; i * i< target; i++){
        int facotrNum = 0;
        while(N % i == 0){
            facotrNum++;
            N /= i;
        }
        if(facotrNum)
            ret.emplace_back(make_pair(i, facotrNum));
    }
    if(N > 1)
        ret.emplace_back(make_pair(N, 1));
    return ret;
}

int main() {
    cin.tie(0);
    int N;
    cin >> N;
    vector<pair<ll, int>> prime = primeFactor(N);
    cout << N << ":";
    for (pair<ll, int> P : prime)
    {
        for (int i = 0; i < P.second; i++){
            cout << " " << P.first;
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3116
#include<cstdio>
#include<queue>
using namespace std;
int main(void)
{
	int n,k;
	while(~scanf("%d%d",&n,&k))
	{
		priority_queue<int,vector<int>,greater<int> >p;
		for(int i=0;i<n;++i)
		{
			int t;
			scanf("%d",&t);
			p.push(t);
		}
		int sum=0;
		for(int i=0;i<k;++i)
		sum+=p.top(),p.pop();
		printf("%d\n",sum);
		while(!p.empty())
		p.pop();
	}
	return 0;
}

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

using namespace std;
int a[200005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=1;i<n;i++){
		if(a[i]==a[i-1]){
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int K=sc.nextInt();

		int syurui=0;

		int[] balls=new int[200001];
		for(int i=0; i<=200000; i++) {
			balls[i]=0;
		}
		int tmp=0;
		for(int i=0; i<N; i++) {
			tmp=sc.nextInt();
			if(balls[tmp]==0) {
				syurui++;
			}
			balls[tmp]++;
		}
		Arrays.sort(balls);
		int tmp1=200000-syurui;
		int kei=0;
		for(int i=tmp1; i<=200000-K; i++) {
			kei+=balls[i];
		}
		System.out.println(kei);
	}
}

Measured memory_bytes: 67200
def main():
    A, B, C = map(int, input().split())
    v = max([A, B, C])
    if v == A:
        return 10*A+B+C
    elif v == B:
        return 10*B+A+C
    else:
        return 10*C+A+B

if __name__ == '__main__':
    print(main())


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define oo 666666666
#define ll long long
#define ld long double

ll mod = 1e9+7;
ll D;
ll DP[100001][2][101];

ll dp(int pos, vector<int>&digits, int pf, ll sum)
{
    if(pos >= digits.size())return sum==0;
    if(DP[pos][pf][sum]!=-1)return DP[pos][pf][sum];
    ll ats = 0;

    for(int j=0; j<=(pf ? digits[pos] : 9); j++)
        {
            ats+=dp(pos+1,digits,pf&(j==digits[pos]),(sum+j)%D);
            ats%=mod;
        }

    return DP[pos][pf][sum]=ats;
}

ll solve(string s)
{
    vector<int>digits;
    for(auto&ch:s)digits.push_back(ch-'0');
    memset(DP, -1, sizeof DP);
    return dp(0,digits,1,0);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string K;
    cin>>K>>D;
    cout<<(solve(K)-1+mod)%mod;
}


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

int c[100];
int main() {
	int n, k;
	while (scanf("%d%d", &n, &k), n) {
		rep(i, n)scanf("%d", &c[i]);
		int a = 0, b = 0;
		int r = 1;
		rep(i, n) {
			if (i - k >= 0)r /= c[i - k];
			r *= c[i];
			a = max(a, r);
		}
		rep(i, n)for (int j = i + 1; j < n; j++) {
			swap(c[i], c[j]);
			r = 1;
			rep(i, n) {
				if (i - k >= 0)r /= c[i - k];
				r *= c[i];
				b = max(b, r);
			}
			swap(c[i], c[j]);
		}
		if (b < a)puts("NO GAME");
		else printf("%d\n", b - a);
	}
}

Measured memory_bytes: 3164
N=int(input())
dp=[float('inf')]*100010
dp[0]=0
base=[1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]


for i in range(N+1):
    for power in base:
        dp[i]=min(dp[i],dp[i-power]+1)

print(dp[N])

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

int main(void){
  int K;
  cin>>K;
  long long array[201]={1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692};
  cout<<array[K-1]<<endl;
  return 0;
}


Measured memory_bytes: 3628
import java.util.*;
import static java.lang.System.*;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  
	  int N = sc.nextInt();
	  int K = sc.nextInt();
	double[] persentList  = new double[N+1]; //各数字ごとの勝利率
	  double sum = 0;
	  int k = K;

	  //1回目で勝ち確定
	  if(N >= K) {
	  for(int i = K; i<=N; i++) 
		  persentList[i] = 1;
	  } else {
		  k = N;
	  }
	  
	  //それ以外
	  for(int i=1; i<=k; i++) {
		  double persent = 1;
		  int count = 0;
		  int n = i;
		  while(n < K) {
			  n *= 2;
			  count++;
		  }
		  for(int j=0; j<count; j++) {
			  persent /= 2;
		  }
		  persentList[i] = persent;
		  
	  }
	  for(int i=1; i<=N; i++) {
		  sum += persentList[i];
	  }
	  
	  double ans = sum  / N;
	  out.println(ans);
	  		  
	}
  }	

Measured memory_bytes: 21716
N = 8
FREE = 0
NOT_FREE = 1
$row = Array.new(N, FREE)
$col = Array.new(N, FREE)
$dpos = Array.new(2*N-1, FREE)
$dneg = Array.new(2*N-1, FREE)
$board = Array.new(N).map { Array.new(N, 0) }

def putQueen(i)
  if i == N
    printBoard
    return
  end
  N.times do |j|
    next if $col[j] ==NOT_FREE || $dpos[i + j] == NOT_FREE || $dneg[i - j + N - 1] == NOT_FREE
    $row[i] = j
    $col[j] = $dpos[i + j] = $dneg[i - j + N - 1] = NOT_FREE
    putQueen i + 1
    $row[i] = $col[j] = $dpos[i + j] = $dneg[i - j + N - 1] = FREE
  end
end

def printBoard
  N.times do |i|
    N.times do |j|
      return if $board[i][j] == 1 && $row[i] != j
    end
  end
  N.times do |i|
    row = ''
    N.times do |j|
      if $row[i] == j
        row << 'Q'
      else
        row << '.'
      end
    end
    puts row
  end
end

n = gets.to_i
n.times do
  input = gets.split(' ').map(&:to_i)
  $board[input[0]][input[1]] = 1
end
putQueen 0


Measured memory_bytes: 8912
def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    X,Y,x,y=map(int, input().split())
    ans = 1 if 2*x==X and 2*y==Y else 0
    print(X*Y/2, ans)


main()

Measured memory_bytes: 3060
x= int(input())

if x%7 == 3:
  print("sun")

elif x%7 == 4:
  print("mon")

elif x%7 == 5:
  print("tue")
  
elif x%7 == 6:
  print("wed")

elif x%7 == 0:
  print("thu")
  
elif x%7 == 1:
  print("fri")
  
elif x%7 == 2:
  print("sat")


Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
// #define f first
// #define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{
	ll A1, A2, A3;
	cin >> A1 >> A2 >> A3;

	if (A1 + A2 + A3 >= 22) cout << "bust" << endl;
	else cout << "win" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
//#include <string>
#include <string.h>
#include <math.h>
//#include <vector>

using namespace std;


int main() {
  int N;
  int A[100];
  int B[100];
  
  int i;
  int a,b; 
  int ans=0;
  int col=0;
  
  cin >> N;
  for(i=0;i<N;i++){
    cin >> A[i];
    B[i] = -1;
  }
  
  a = 0;
  b = 0;
  
  for(i=1;i<N;i++){
    if(A[i]==A[i-1]){
      b=i;
    }else{
      B[col]=b-a;
      col++;
      a = i;
      b = i;
    }
  }
  B[col]=N-1-a;
  col++;
  
  for(i=0;i<col;i++){
    //    printf("%d\n",B[i]);
    ans += (int)((B[i]+1)/2);
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int items,price[15],i,TotalCost,pos;
    cin>>items;
    for(i=1;i<=items;i++)
        cin>>price[i];
    int highest = price[1];
    for(i=2;i<=items;i++)
    {
        if(price[i]>=highest)
        {
            highest = price[i];
            pos = i;
        }
    }
    TotalCost = (highest)/2;
    for(i=1;i<=items;i++)
    {
        if(i!=pos)
            TotalCost+=price[i];
    }
    cout<<TotalCost<<endl;
    return 0;
}


Measured memory_bytes: 256
while True:
	n=input().split()
	n[0]=int(n[0])
	n[1]=int(n[1])
	if n[0]==0 and n[1]==0:
		break

	if n[0]>n[1]:
		c=n[0]
		n[0]=n[1]
		n[1]=c
	print(n[0],n[1])


Measured memory_bytes: 5608
#include <iostream>
#define nmax 105
#define kmax 100005
using namespace std;
int n, k, a[nmax], sg[kmax];
 
 
int main()
{
 	int i, j;
 	cin >> n >> k;
    for (i = 1; i <= n; i++)
    	cin >> a[i];
 
	for (i = 0; i < a[1]; i++)
     	sg[i] = 0;
  	for (i = a[1]; i <= k; i++)
    	for (j = 1; j <= n; j++)
          	if (i - a[j] >= 0 && sg[i - a[j]] == 0)
              sg[i] = 1;
  	if (sg[k])
      cout << "First\n";
  	else
      cout << "Second\n";
 	
  	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main() {
	int N, K;
	cin >> N >> K;
	vector<ll>num(K,0);
	for (int i = 1; i <= N; ++i) {
		num[i%K]++;//num[x]=kで割ってx余る数が1以上N以下に何個あるか
	}
	ll res = 0;
	for (int a = 0; a < K; ++a) {
		int b = (K - a) % K;
		int c = (K - a) % K;
		if ((b + c) % K != 0)continue;
		res += num[a] * num[b] * num[c];
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<iostream>
#include<ctype.h>
#include<string>
using namespace std;
int main(){
	int n, c = 1;
	cin >> n;
	int h[n];
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	for(int i = 1; i < n; i++){
		for(int s = 0; s < i; s++){
			if(s == i - 1){
				if(h[i] >= h[s]){
					c++;
				}
				else{
					break;
				}
			}
			else if(h[i] >= h[s]){
				continue;
			}
			else{
				break;
			}
		}
	}
	cout << c << endl;
	return 0;
}

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

fn main() {
    let n: usize = read();
    let mut grid = Vec::new();
    for _ in 0..n {
        let s: String = read();
        let s = s.chars().collect::<Vec<_>>();
        grid.push(s);
    }
    // println!("{:?}", grid);

    let mut ans = 0;
    for a in 0..n {
        let mut success = true;
        for i in 0..n {
            for j in 0..n {
                if grid[i][(j + a) % n] != grid[j][(i + a) % n] {
                    success = false;
                }
            }
        }
        if success {
            ans += 1
        }
    }
    ans *= n;
    println!("{:?}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;
 
string str;
 
int main()
{
  int n,i,j,k,l,m,a,b;
  int number[10][10];
  bool wrong[10][10];//wrong??????true*
  int check[10]={};
  
  cin>>n;
 
  rep(i,n){
    if(i)cout<<endl;
    rep(j,9)rep(k,9){
      wrong[j][k]=false;
      scanf("%d",&number[j][k]);
    }
 
    rep(j,9){//yoko check
      rep(k,10)
    check[k]=0;//0???§?????????
      rep(k,9){
    check[number[j][k]]++;
    if(check[number[j][k]]>1){//2nd
      rep(l,9)
        if(number[j][l]==number[j][k])
          wrong[j][l]=true;
         
    }
      }//repk
    }//repj
     
 
    rep(k,9){//tate check
      rep(j,10)
    check[k]=0;//?????????
      rep(j,8){
    for(l=j+1;l<9;l++)
      if(number[j][k]==number[l][k]){
        wrong[j][k]=true;
        wrong[l][k]=true;
      }
      }//repj
    }//repk
     
    rep(j,3){//block check
      rep(k,3){
    rep(l,10)
      check[l]=0;//?????????
    rep(l,3)
      rep(m,3){
      check[number[3*j+l][3*k+m]]++;
      if(check[number[3*j+l][3*k+m]]>1){//2nd
        rep(a,3)
          rep(b,3)
          if(number[3*j+a][3*k+b]==number[3*j+l][3*k+m])
        wrong[3*j+a][3*k+b]=true;
           
      }
    }
      }//repk
    }//repj
 
    rep(j,9){
      rep(k,9){
    if(wrong[j][k])
      cout<<"*";
    else
      cout<<" ";
    cout<<number[j][k];
      }
      cout<<endl;
    }
 
 
  
  }
}

Measured memory_bytes: 1240
#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>;
const ll N = pow(10, 9);
 
int main() {
  int k;
  cin >> k;
  set<int> s;
  int x = 7 % k;
  int i = 1;
  while(s.count(x) == 0) {
    if(x == 0) {
      cout << i << endl;
      return 0;
    }
    s.insert(x);
    x = (x*10 + 7)%k;
    i++;
  }
  cout << -1 << endl;
  return 0;
}
    

Measured memory_bytes: 50428
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw				"\n"


int main(void)
{
	CIN;
	ll tc,l,k,sum=0,x=0,y,z=0,m=1,n=0,ans=0;
	char c;
	while(cin>>c)
	{
		if(c=='A'||c=='G'||c=='C'||c=='T'){
			sum++;
			if(ans<sum)ans=sum;
		}
		else sum=0;
	}
	cout<<ans<<nw;
}


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

int main(){
  int n;cin>>n;
  ll ans=(ll)1e12;
  vector<ll> x(n,0);
  REP(i,n) cin>>x.at(i);
  sort(x.begin(),x.end());

  for(ll i=x.at(0);i<=x.at(n-1);i++){
    ll dis=0;
    REP(j,n){
      dis+=(x.at(j)-i)*(x.at(j)-i);
    }
    ans=min(ans,dis);
  }
  
  cout<<ans;
}

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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
using intmap = map<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
inline bool bit (ll b, ll i) { return b & (1 << i); }
inline ll ceiv (ll a, ll b) { return (a + b - 1) / b; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define debug(x) cerr << #x << ": " << x << '\n'
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()

signed main(){
    int n; cin >> n;
    vi ans(n+1, 0);
    for(int x = 1; x * x <= n; x++){
        for(int y = 1; y * x <= n - x*x; y++){
            for(int z = 1; z * z <= n - x*x - y*y - x*y; z++){
                int f = x*x + y*y + z*z + x*y + y*z + x*z;
                if(0 < f && f <= n){
                    ans[f]++;
                }
            }
        }
    }
    reps(i,1,n) cout << ans[i] << endl;
}

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

int main(){
    int n,p;
    while(cin>>n>>p){
        if(n==0)break;
        int s[n];
        memset(s,0,sizeof(s));
        ll cnt=0;
        ll ss=p;
//        ll i=0;
        bool flag=false;
        while(1){
            for(ll i=0;i<n;i++){
                if(p>0){
                    s[i]++;
                    p--;
                }else{
                    ll a = s[i];
                    s[i]=0;
                    p+=a;
                }
                if(p==0){
                    for(int i=0;i<n;i++){
                        if(s[i]==ss){
                            flag=true;
                            cnt=i;
                            break;
                        }
                    }
                }
                if(flag)break;
            }
            // for(int i=0;i<n;i++){
            //     cout<<"s:"<<s[i]<<endl;
            // }
            if(flag)break;
        }
        cout<<cnt<<endl;
    }
}


Measured memory_bytes: 3008
def main():
    S = list(input())
    tmp = list('keyence')
    st = -1; ed = -1
    if S[0] == tmp[0]:
        st = 0
        for i in range(1, len(tmp)):
            if S[i] == tmp[i]:
                st += 1
            else:
                break
    if st+1 == len(tmp):
        print('YES')
        return
    if S[-1] == tmp[-1]:
        ed = 0
        for i in range(1, len(tmp)):
            if S[-1-i] == tmp[-1-i]:
                ed += 1
            else:
                break
    if ed+1 == len(tmp):
        print('YES')
        return
    if st == -1 or ed == -1:
        print('NO')
        return
    rm = (st+1 + ed+1) - len(tmp)
    if rm >= 0:
        s = tmp[:st+1] + tmp[-ed-1+rm:]
        if s == tmp:
            print('YES')
    else:
        print('NO')

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<iomanip>
#include<vector>
typedef unsigned long long ull;
typedef signed long long sll;
using namespace std;

#define INF 0x7FFFFFFFFFFFFFFF
#define BIG_PRIME 1000000007

vector<sll> a;
vector<vector<sll>> dp;

sll get_dp(int l,int r)
{
  if(l==r)return 0;
  if(dp[l][r]==INF)
  {
    dp[l][r]=max(a[l]-get_dp(l+1,r),a[r-1]-get_dp(l,r-1));
  }
  return dp[l][r];
}

int main()
{
  ull i,j,N;
  cin >> N;
  a.resize(N);
  dp.resize(N+1);
  for(i=0;i<=N;++i)
  {
    dp[i].resize(N+1,INF);
    if(i<N)
    {
      cin >> a[i];
    }
  }
  cout << get_dp(0,N);
  return 0;
}

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

using namespace std;

int n;
multiset< pair<long long, long long> > sl, sr, tl, tr;

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	while (n--) {
		long long l, r; 
		cin >> l >> r;
		sl.insert({l, r});
		sr.insert({r, l});
	}
	long long cur, res, mx;
	mx = 0;
	{
		cur = res = 0;
		tl = sl, tr = sr;
		while (tl.size()) {
			auto ir = tr.begin();
			auto il = --(tl.end());
			if (ir -> first < cur) {
				res += cur - ir -> first, cur = ir -> first;
				tl.erase(tl.find({ir -> second, ir -> first}));
				tr.erase(ir);
				continue;
			}
			if (il -> first > cur) {
				res += il -> first - cur, cur = il -> first;
				tr.erase(tr.find({il -> second, il -> first}));
				tl.erase(il);
				continue;
			}
			break;
		}
		res += abs(cur);
	}
	mx = max(mx, res);
	{
		cur = res = 0;
		tl = sl, tr = sr;
		while (tl.size()) {
			auto ir = tr.begin();
			auto il = --(tl.end());
			if (il -> first > cur) {
				res += il -> first - cur, cur = il -> first;
				tr.erase(tr.find({il -> second, il -> first}));
				tl.erase(il);
				continue;
			}
			if (ir -> first < cur) {
				res += cur - ir -> first, cur = ir -> first;
				tl.erase(tl.find({ir -> second, ir -> first}));
				tr.erase(ir);
				continue;
			}
			break;
		}
		res += abs(cur);
	}
	mx = max(mx, res);
	cout << mx;
}

Measured memory_bytes: 25216
/*
 FF外から失礼するゾ～（謝罪）
 このツイート面白スギィ！！！！！
 自分、RTいいっすか？
 淫夢知ってそうだから淫夢のリストにぶち込んでやるぜー
 いきなりリプしてすみません！
 許してください！なんでもしますから！(なんでもするとは言ってない)
*/
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int res = INF;

    rep(cut, 1 << (h-1)) {
        int g = 0;
        vec id(h);
        rep(i, h) {
            id[i] = g;
            if ((cut >> i) & 1) g++;
        }
        g++;

        mat c(g, vec(w, 0));
        rep(i, h) rep(j, w) c[id[i]][j] += (s[i][j] - '0');

        int ress = g-1;
        vec now(g);
        auto add = [&](int j) {
            rep(i, g) now[i] += c[i][j];
            rep(i, g) if (now[i] > k) return false;
            return true;
        };
        rep(j, w) {
            if (!add(j)) {
                ress++;
                now = vec(g);
                if (!add(j)) {
                    ress = INF;
                    break;
                }
            }
        }
        res = min(res, ress);
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> mov;

char S[8][8];

bool isin(int y, int x) {
  return 0 <= y && y < 8 && 0 <= x && x < 8;
}

int main(void) {
  REP(i, 0, 8) cin >> S[i];

  char me = 'o';
  char op = me == 'x' ? 'o' : 'x';
  char em = '.';
  int pass = 0;
  while(1) {
    int ans = 0, ay = -1, ax = -1;
    vector<mov> mv;
    REP(i, 0, 8) REP(j, 0, 8) {
      if(S[i][j] != em) continue;
      int cnt = 0;
      vector<mov> v;
      REP(k, -1, 2) REP(l, -1, 2) {
        int y = i, x = j;
        if(k == 0 && l == 0) continue;
        int q = 0;
        while(1) {
          y += k;
          x += l;
          if(!isin(y, x)) break;
          if(S[y][x] == op) q++;
          else break;
        }
        if(!(isin(y, x) && S[y][x] == me)) q = 0;
        cnt += q;
        if(q > 0) v.push_back(mov(pii(k, l), q));
      }
      if((me == 'o' && ans < cnt) || (me == 'x' && ans <= cnt)) {
        mv = v;
        ans = cnt;
        ay = i;
        ax = j;
      }
    }
    if(mv.size() > 0) {
      S[ay][ax] = me;
      REP(i, 0, mv.size()) {
        int y = ay, x = ax;
        REP(j, 0, mv[i].se) {
          y += mv[i].fi.fi;
          x += mv[i].fi.se;
          S[y][x] = me;
        }
      }
      pass = 0;
    } else {
      if(pass == 1) break;
      pass = 1;
    }
    swap(me, op);
  }

  REP(i, 0, 8) {
    REP(j, 0, 8) cout << S[i][j];
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

char endof(char* s) {
	int i = 0;
	while (s[i] != '\0') {
		i++;
	}
	i--;
	return s[i];
}

int main()
{
	int N;
	char s[100][11];

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

	int flg = 0;
	for (int i = 0; i < N-1; i++) {
		if (endof(s[i]) == s[i + 1][0]) {//成功
			;
		}
		else {// 失敗
			flg = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) {
				;
			}
			else if(strcmp(s[i], s[j]) == 0) {
				flg = 1;
			}
		}
	}
	if (flg) {
		cout << "No\n";
	}
	else {
		cout << "Yes\n";
	}
}

Measured memory_bytes: 256
n, m = map(int, input().split())
xyz = [tuple(map(int, input().split())) for _ in range(n)]
ans = 0
from itertools import product
for p in product([-1, 1], repeat=3):
    xyz_ = map(lambda l: l[0]*p[0] + l[1]*p[1] + l[2]*p[2], xyz)
    xyz_ = sorted(xyz_, reverse=True)
    ans = max(ans, sum(xyz_[:m]))
print(ans)


Measured memory_bytes: 68320
#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int, int> P;
int w[105], v[105];
signed main() {
	int n, W; cin >> n >> W;
	rep(i, n)cin >> w[i] >> v[i];
	vector<int>v1, v2, v3, v4;
	rep(i, n) {
		if (w[i] - w[0] == 0)v1.push_back(v[i]);
		if (w[i] - w[0] == 1)v2.push_back(v[i]);
		if (w[i] - w[0] == 2)v3.push_back(v[i]);
		if (w[i] - w[0] == 3)v4.push_back(v[i]);
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	sort(v3.begin(), v3.end());
	sort(v4.begin(), v4.end());
	v1.push_back(0); v2.push_back(0); v3.push_back(0); v4.push_back(0);

	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	reverse(v3.begin(), v3.end());
	reverse(v4.begin(), v4.end());
	rep(i, v1.size() - 1)v1[i + 1] += v1[i];
	rep(i, v2.size() - 1)v2[i + 1] += v2[i];
	rep(i, v3.size() - 1)v3[i + 1] += v3[i];
	rep(i, v4.size() - 1)v4[i + 1] += v4[i];

	int ans = 0;
	rep(i, v1.size()) {
		rep(j, v2.size()) {
			rep(k, v3.size()) {
				rep(l, v4.size()) {
					int we = i * w[0] + j * (w[0] + 1) + k * (w[0] + 2) + l * (w[0] + 3);
					if (we <= W)ans = max(ans, v1[i] + v2[j] + v3[k] + v4[l]);
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>          // printf(), putchar(), scanf()

int
main(int argc, char **argv)
{
	const double height[5] = {165.0, 170.0, 175.0, 180.0, 185.0};
	int bins[6];

	for (int i = 0; i < 6; ++i)
		bins[i] = 0;

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		double d;
		scanf("%lf", &d);

		int j;
		for (j = 0; j < 5; ++j)
		{
			if (d < height[j])
				break;
		}

		bins[j]++;
	}

	for (int i = 0; i < 6; ++i)
	{
		printf("%d:", i + 1);
		for (int j = 0; j < bins[i]; ++j)
			putchar('*');

		putchar('\n');
	}

	return 0;
}

Measured memory_bytes: 1816
#include<iostream>
#include<string>
#include <cmath>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
int main(){
 
int n;
cin >> n;
 
int d[1010] = {0};
for(int i = 2; i <= n; i++){
int num = i;
 for(int j = 2; j <= n; j++){
  while(num % j == 0){
   d[j]++;
   num /= j;
  }
 }
}
 
ll ans = 1;
 
for(int i = 0; i <= n; i++){
ans *= (d[i] + 1);
ans %= MOD;
}
 
cout << ans << endl;
 
return 0;
}

Measured memory_bytes: 256