akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll max_E=100000;
const ll max_V=100000;
ll INF=9000000000000000000;

struct edge{ll from,to,cost;};

edge es[max_E];
ll dist[max_V];
ll N,M;
bool negative[max_V];

void shortest_path(ll s){
    fill(negative,negative+N,0);
    for(int i=0;i<N;i++) dist[i]=INF;//INFを作る
    dist[s]=0;
    for(int loop=0;loop<N-1;loop++){
        for(int i=0;i<M;i++){
            edge e=es[i];
            if(dist[e.from]==INF) continue;
            if(dist[e.from]!=INF&&dist[e.to]>dist[e.from]+e.cost){
                dist[e.to]=dist[e.from]+e.cost;
            }
        }
    }
}

void find_negative_loop(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            edge e=es[j];
            if(dist[e.from]==INF) continue;
            if(dist[e.to]>dist[e.from]+e.cost){
                dist[e.to]=dist[e.from]+e.cost;
                negative[e.to]=1;
            }
            if(negative[e.from]) negative[e.to]=1;
        }
    }
}

int main(){
    cin>>N>>M;
    for(ll i=0;i<M;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        es[i].from=a;
        es[i].to=b;
        es[i].cost=-c;
    }
    shortest_path(0);
    find_negative_loop();
    if(negative[N-1]) cout<<"inf"<<endl;
    else{
        cout<<-dist[N-1]<<endl;
    }
}

Measured memory_bytes: 256
import scala.io.StdIn

object Main extends App {

  val n = StdIn.readLine().toInt
  val M = Array.fill[Int](n, n)(Int.MaxValue)

  (0 until n).foreach { _ =>
    val a = StdIn.readLine().split(' ').map(_.toInt)
    (0 until a(1)).foreach { k =>
      M(a(0))(a(2 + k * 2)) = a(2 + k * 2 + 1)
    }
  }

  // (0 until n).foreach { i => println(M(i).mkString("")) }
  private val WHITE = 0
  private val GRAY = 1
  private val BLACK = 9

  val color = Array.fill[Int](n)(WHITE)
  val distance = Array.fill(n)(Int.MaxValue)
  val parent = Array.fill(n)(-1)

  def dijkstra(s: Int): Unit = {
    var mincost = -1
    var u = 0
    distance(s) = 0
    parent(s) = -1

    while (mincost != Int.MaxValue) {
      mincost = Int.MaxValue
      (0 until n).foreach { i =>
        if (color(i) != BLACK && distance(i) < mincost) {
          mincost = distance(i)
          u = i
        }
      }

      if (mincost != Int.MaxValue) {
        color(u) = BLACK

        (0 until n).foreach { v =>
          if (color(v) != BLACK && M(u)(v) != Int.MaxValue) {
            if (distance(u) + M(u)(v) < distance(v)) {
              distance(v) = distance(u) + M(u)(v)
              parent(v) = u
              color(v) = GRAY
            }
          }
        }

      }

    }
  }

  dijkstra(0)

  (0 until n).foreach(i => println(i + " " + distance(i)))

}




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

int main(){
  int N;
  cin >> N;
  vector<int64_t> A(N);
  bool flag=false;
  int count=0;
  int64_t ans=0;
  int64_t a;
  for(int i=0;i<N;i++){
    cin >> a;
    if(a==0){
      flag=true;
    }
    if(a<0){
      count++;
    }
    A.at(i)=abs(a);
  }
  if(flag){
    for(int i=0;i<N;i++){
      ans+=A.at(i);
    }
    cout << ans << endl;
  }else{
    if(count%2==0){
      for(int i=0;i<N;i++){
        ans+=A.at(i);
      }
      cout << ans << endl;
    }else{
      sort(A.begin(),A.end());
      ans-=A.at(0);
      for(int i=1;i<N;i++){
        ans+=A.at(i);
      }
      cout << ans << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int a,b,x[7]={1,3,5,7,8,10,12},y[4]={4,6,9,11},i,c=0,c2=0,d=0,d2=0,e=0,e2=0,flg=0;
	scanf("%d%d",&a,&b);
	for(i=0;i<7;i++){
		if(a==x[i]) c=1;
		if(b==x[i]) c2=1;
	}
	if(c==1&&c2==1) flg=1;
	for(i=0;i<4;i++){
		if(a==y[i]) d=1;
		if(b==y[i]) d2=1;
	}
	if(d==1&&d2==1) flg=1;
	if(a==2) e=1;
	if(b==2) e2=1;
	if(e==1&&e2==1) flg=1;
	if(flg==1) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 1624
n,m = map(int,input().split())

a_list = []
b_list = []
c_list = []

for a in range(n):
    a_list.append(list(map(int,input().split())))

for b in range(m):
    b_list.append(int(input()))

for c in range(n):
    c_list.append([])
    for d in range(m):
        c_list[c].append((a_list[c][d] * b_list[d]))

c_list = list(map(sum,c_list))

for c in c_list:
    print(c)

Measured memory_bytes: 8384
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
a = [int(input()) for _ in range(5)]

min_num = a[0]

for i in a:
	if i < min_num:
		min_num = i
		
ans = -(-N // min_num) + 4
print(ans)


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

bool dbgflag = false;

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

  ll N;
  cin >> N;

  const ll MAXN = 3500;
  for (ll i = 1; i <= MAXN; i++) {
    for (ll j = 1; j <= MAXN; j++) {
      if ((4*i*j - N*i - N*j > 0) && ((N*i*j) % (4*i*j - N*i - N*j) == 0)) {
        cout << i << " " << j << " " << (N*i*j) / (4*i*j - N*i - N*j) << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#include <iomanip>
#include <math.h>
#include <cmath>

#define PI 3.14159265359

using namespace std;
#define ASCII 97


int main() {
	long int K;
	int N, Q;
	cin >> N >> K >> Q;

	int* score = new int[N]();

	for (int i = 0; i < Q; i++) {
		int index;
		cin >> index;
		index -= 1;
		score[index]++;
	}

	for (int i = 0; i < N; i++) {
		if (K - (Q - score[i]) > 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

}



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

int dp[1002][1002];

int main() {
    int n;
    while (scanf("%d", &n), n) {
        int ret = 0;
        char line[1001];
        for (int i=1; i<=n; ++i) {
            scanf("%s", line);
            for (int j=0; j<n; ++j) {
                if (line[j] == '.') {
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    ret = max(ret, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Measured memory_bytes: 5108
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
char s[1000];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    int ans=0;
    for(int i=0;i<len/2;i++)
    {
        if(s[len-i-1]!=s[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>string join(const vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T>ostream& operator<<(ostream& o, const vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, const vector<vector<T> >&vv)
{int l=vv.size();if(l){o<<endl;rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

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

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const ll INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

#define M 2000

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    string a,b,c;
    cin >> a >> b >> c;
    int A = a.size();
    int B = b.size();
    int C = c.size();

    auto match = [&](char c1, char c2){
        return (c1 == '?' || c2 == '?' || c1 == c2);
    };

    vi ab(100000), ac(100000), bc(100000);
    rep(i,A) rep(j,B) if(!match(a[i], b[j])) ab[i-j+50000] = 1;
    rep(i,A) rep(j,C) if(!match(a[i], c[j])) ac[i-j+50000] = 1;
    rep(i,B) rep(j,C) if(!match(b[i], c[j])) bc[i-j+50000] = 1;

    int ans = 3 * M;
    REP(i,-2*M,2*M+1) REP(j,-2*M,2*M+1){
        if(!ab[i+50000] && !ac[j+50000] && !bc[j-i+50000]){
            int l = min(0, min(i, j));
            int r = max(A, max(B + i, C + j));
            ans = min(ans, r - l);
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{	
	int n,x;
	scanf("%d %d",&n,&x);
	int vals[n+1];
	for(int i = 0; i < n; i++)
	{
		scanf("%d",&vals[i]);
	}	
	vals[n] = x;
	sort(vals, vals + n + 1);
	int dis[n];
	for(int i = 1; i < n + 1 ; i++)
	{
		//cout<<dis[i-1]<<endl;
		dis[i-1] = vals[i] - vals[i-1];
		//cout<<dis[i-1]<<endl;
	}
	int res = dis[0];
	for(int i = 1; i < n ; i++)
	{
		res = __gcd(dis[i],res);
	}
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int ans = 0;
	int i, n,tmp;
	vector<int> d;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> tmp;
		d.push_back(tmp);
	}

	sort(d.begin(), d.end());

	ans = max(0, d[n / 2] - d[n / 2 - 1]);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define PI 3.14159265358979323846264338327950L
using namespace std;
int main(){
  long double a,b,h,m; cin >> a >> b >> h >> m;
  long double rad = (h/12 + (m /60)/12 - m/60) * 2 * PI;
  long double c = a * a + b * b - 2 * a * b * cos(rad);
  printf("%.20Lf\n",sqrt(c));
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

using llong = long long int;

const static int MOD = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = 1LL << 31;
const static int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;
    int n = (int)S.size();
    vector<int> children_cnt(n, 0);

    int right_pos = 0;
    rep(i, n) {
        if (S[i] == 'R') {
            right_pos = i;
        } else {
            if ((i - right_pos) % 2 == 0) ++children_cnt[right_pos];
            else ++children_cnt[right_pos + 1];
        } 
    }

    int left_pos = n - 1;
    rep(i, n) {
        if (S[n - i - 1] == 'L') {
            left_pos = n - i - 1;
        } else {
            if ((left_pos - (n - i - 1)) % 2 == 0) ++children_cnt[left_pos];
            else  ++children_cnt[left_pos - 1];
        }
    }

    rep(i, n) {
        if (i == n - 1) cout << children_cnt[i] << endl;
        else cout << children_cnt[i] << " ";
    }
    
    return 0;
}

Measured memory_bytes: 1104
import java.util.Scanner;

//A first Grader
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++)a[i]=sc.nextInt();
		long[][] dp = new long[n-1][21];
		dp[0][a[0]] = 1;
		for(int i=1;i<n-1;i++){
			for(int p=0;p<=20;p++){
				long sum = 0;
				if(0<=p-a[i]&&p-a[i]<=20)sum+=dp[i-1][p-a[i]];
				if(0<=p+a[i]&&p+a[i]<=20)sum+=dp[i-1][p+a[i]];
				dp[i][p] = sum;
			}
		}
		System.out.println(dp[n-2][a[n-1]]);
	}
}

Measured memory_bytes: 12000
#include<stdio.h>
#define PMAX 1000000000
int wmax=0;
int n,k,w[100000];
 
int check(int P){
    int i;
    int count=1,now=P;
    if(P<wmax) return 0;
    for(i=0;i<n;i++){
        if(now>=w[i]){
           now-=w[i];
        }else{
            count++;
            now=P-w[i];
        }
    }
    if(count>k) return 0;
    else return 1;
}
 
int main(void){
    int i;
    int left,right,mid;
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&w[i]);
        if(w[i]>wmax) wmax=w[i];
    }
 
    left=0,right=PMAX;
    while(right-left>1){
        mid=(left+right)/2;
        if( check(mid) ) right=mid;
        else left=mid;
    }
    printf("%d\n",right);
    return 0;
}


Measured memory_bytes: 2172
n,k = map(int,input().split())
sss = input()

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if len(x) % 2 == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

left = 0
right = 0
tmp = 0

for i in range(len(x))[::2]:
    nextleft = i
    nextright = min(i + Add, len(x))
    while nextleft > left:
        tmp -= x[left]
        left += 1
    while nextright > right:
        tmp += x[right]
        right += 1
    
    ans = max(tmp, ans)

print(ans)

Measured memory_bytes: 4212
#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,m;
  cin >> n >> m;
  vector<int> L(m);
  vector<int> R(m);
  int ans = 0;
  rep(i,m){
    cin >> L[i] >> R[i];
  }
  sort(L.rbegin(),L.rend());
  sort(R.begin(),R.end());
  cout << max(0,R[0]-L[0]+1) << endl;
  return 0;
}


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

public class Main
{
  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    
    String sl[] = r.readLine().split(" ");
    long a = Long.parseLong(sl[0]);
    long b = Long.parseLong(sl[1]);
    long c = Long.parseLong(sl[2]);
    long k = Long.parseLong(sl[3]);

    System.out.println(k % 2 == 0 ? a - b : b - a);

  }
}


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

int main() {
int K;
  string S;
  cin>>K;
  cin>>S;
  if(S.size()<=K){
    cout<<S<<endl;
  }
  if(S.size()>K){
    for(int i=0;i<K;i++){
      cout<<S.at(i);
    }
    cout<<"..."<<endl;
  }
}


Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
#include <fstream>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>
using namespace std;
typedef int64_t ll;
typedef uint64_t ull;
constexpr uint64_t L1 = 1ull;
constexpr ull bit(int n){ return 1ull << n;}

constexpr ll INF       = 1000000000;/* 1e+9a */

void solve(istream& cin) {
    int N;
    while(cin >> N){
        ll sum = 0;
        ll maxi = 0;
        for (int i = 0; i < N; ++i) {
            ll tmp;
            cin >> tmp;
            sum += tmp;
            maxi = max(maxi, tmp);
        }// i
        sum -= maxi / 2;
        
        cout << sum << '\n';
    
    }
}

int main(int argc, char *argv[]) {
    string FileName("B"), Modifier("_MEPH");
    string ExecutionName = FileName + Modifier;
    string sub(argv[0]);
    // pass消去
    if(sub.size() > ExecutionName.size())
        sub = sub.substr(sub.size()-ExecutionName.size(), ExecutionName.size());

	// 数値計算もの用
    cout << setprecision(16) << scientific;
    if (sub != ExecutionName) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        solve(cin);
    }
    else {    
	    cerr << sub << endl;
        string inFile = "B_sample.txt";
        auto fs = fstream(inFile, fstream::in);
        solve(fs);
    }
}


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

int main() {
    ll n,x;
    cin>>n>>x;
    vector<ll> l(n);
    rep(i,n)cin>>l[i];
    vector<ll> d(n+1);
    d[0]=0;
    ll sum=0;
    sum++;
    for(ll i=1;i<n+1;i++){
        d[i]=d[i-1]+l[i-1];
        if(d[i]<=x)sum++;
    }
    cout<<sum<<endl;
}


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

int main()
{
	long long n,ans=0; cin>>n;
	for(long long l=1,r;l<=n;l=r+1) {
    	r=n/(n/l);
    	long long t=n/(n/l)-1;
    	if (l<=t && t<=r && n%t==n/t) ans+=t;
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(void){
    using namespace std;
    int a;

    cin >> a;

    int a_l[a];
    int max = 0;
    int min = pow(10, 9);

    int now_num = 0;

    for(int i=0; i < a; i++){
        cin >> now_num;
        if(now_num > max){
            max = now_num;
        }
        if (now_num < min){
            min = now_num;
        }
    }
    
    cout << max - min << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
typedef long long int ll;
typedef long double ld;

int main(void){
	ll A, res;
	float b;
	std::cin >> A >> b;
	float B = std::round(b * 100);
	res = A * B / 100;
	
	std::cout << res << std::endl;
	return 0;
}
// WA, AC with answer


Measured memory_bytes: 3688
def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

def lcm(m,n):
    return(m * n // gcd(m,n))

a,b,c,d = map(int,input().split())
a -= 1

sb1 = b // c
sb2 = b // d
sb3 = b // lcm(c,d)

b2 = b - sb1 - sb2 + sb3

sa1 = a // c
sa2 = a // d
sa3 = a // lcm(c,d)

a2 = a - sa1 - sa2 + sa3

print(b2-a2)

Measured memory_bytes: 3064
# coding: utf-8
def main():
    _min, _max = 123, 0
    for _ in range(5):
        i = int(input())
        if _min > i:
            _min = i
        if i > _max:
            _max = i
    k = int(input())

    print(":(" if _max-_min > k else "Yay!")


main()

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

  int y = 0;
  string name = "kogakubu10gokan";

  for (int i = 0; i < n; i++) {
    int ty;
    string tname;
    cin >> ty >> tname;
    if (y <= q && q < ty) {
      cout << name << endl;
      return 0;
    }
    y = ty;
    name = tname;
  }
  cout << name << endl;

  return 0;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define deb(x)     cerr << (#x) << " : " << (x) << "\n"
#define ll long long int
#define ld long double
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
using namespace std;

ll powmod(ll a, ll b, ll MOD = MOD){
	if(!a and !b)	return 1ll;
	if(!a)	return a;
	ll res = 1ll;
	b %= (MOD - 1ll), a %= MOD;
	while(b){
		if(b%2 == 1)	res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

ll dp[5010][5010];	

int main(){	

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

	int n;
	cin >> n;

	pair<ll, ll> arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i].first >> arr[i].second;
		arr[i].first += arr[i].second;
	}

	sort(arr, arr + n);
	for(int i = 0; i < n; i++)	arr[i].first -= arr[i].second;

	for(int i = 0; i <= n; i++)	for(int j = 0; j <= (n+2); j++)	dp[i][j] = INF;

	dp[0][0] = 0;
	deb(dp[1][1]);

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= (i + 1); j++){
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			if(dp[i][j] <= arr[i].first)
				dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + arr[i].second);
			// cout << dp[i][j] << " ";
		}
		// cout << endl;
	}

	for(int i = n; i >= 0; i--){
		if(dp[n][i] != INF){
			cout << i << "\n";
			return 0;
		}
	}

	cout << 0 << "\n";
}

Measured memory_bytes: 196224
#include <bits/stdc++.h> 
#define ll long long int
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
 
using namespace std; 
 
 
int main() 
{
    int n;
    cin>>n;

    string a,b;
    cin>>a>>b;

    for(int i=0;i<n;i++) {
        cout<<a[i]<<b[i];
    }
    cout<<endl;
}

Measured memory_bytes: 256
import math

text = input()
reply = "Yes"

if text != text[::-1]:
    reply = "No"

tmp = text[0:math.floor((len(text) - 1) / 2)]
if tmp != tmp[::-1]:
    reply = "No"

text=text[::-1]
tmp = text[0:math.floor((len(text) - 1) / 2)]
if tmp != tmp[::-1]:
    reply = "No"

print(reply)

Measured memory_bytes: 38384
<?php

fscanf(STDIN, "%d", $n);

$table = array();
$total = 0;

for($i = 0; $i < $n; $i++){
    
    $str = trim(fgets(STDIN));
    $backet = array_fill(0, 30, 0);
    for($j = 0; $j < 10; $j++){
        $backet[ord(substr($str, $j, 1)) - ord("a")]++;
    }
    
    $newstr = "";
    for($j = 0; $j < 26; $j++){
        for($k = 0; $k < $backet[$j]; $k++){
            $newstr = $newstr . chr($j + ord("a"));
        }
    }
    
    if(array_key_exists($newstr, $table)){
        $table[$newstr]++;
        $total += $table[$newstr];
    }else{
        $table[$newstr] = 0;
    }
}

echo $total;

?>

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N, C;
vector<pii> T[31];
int imos[30][100010];

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

	cin >> N >> C;
	int s, t, c;
	rep(i, 0, N)
	{
		cin >> s >> t >> c;
		c--;
		T[c].push_back(mp(s, t));
	}

	rep(i, 0, C)
	{
		if (T[i].empty())continue;
		rep(j, 0, SZ(T[i]))
		{
			imos[i][T[i][j].first - 1]++;
			imos[i][T[i][j].second]--;
		}
		rep(j, 0, 100005)
		{
			imos[i][j + 1] += imos[i][j];
		}
	}

	int ans = 0;
	rep(i, 0, 100010)
	{
		int res = 0;
		rep(j, 0, C)
		{
			if (imos[j][i])res++;
		}
		chmax(ans, res);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 26240
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char s[5];
	int ans=0;
	scanf("%s",s+1);
	if(s[2]=='R'&&s[2]==s[1]&&s[2]==s[3]) ans=3;
	else if(s[2]=='R'&&s[1]==s[2]) ans=2;
	else if(s[2]=='R'&&s[2]==s[3]) ans=2;
	else if(s[1]=='R'||s[2]=='R'||s[3]=='R') ans=1;
	else ans=0;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3824
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	int n = 0;
	for (int i = a; i <= b; i++) {
		if (c % i == 0) {
			n++;
		}
	}
	cout << n << endl;
	return 0;
}



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

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

int sum=0;
if(a==b&&a!=c){
  sum=1;
}else if(a==c&&a!=b){
  sum=1;
}else if(b==c&&a!=b){
  sum=1;
}
  
if(sum==1){
System.out.println("Yes");
}else{
  System.out.println("No");
}
}
}

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

using ll = long long;

int main()
{
    int N;
    vector<ll> A;
    vector<ll> B;
    cin >> N;
    A.resize(N);
    B.resize(N, 0LL);

    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        if(i - 1 >= 0)
        {
            B[i] = A[i] + B[i - 1];
        }
        else
        {
            B[i] += A[i];
        }
    }

    sort(B.begin(), B.end(), greater<ll>());

    ll v = B[0];
    ll cnt = v == 0 ? 2 : 1;
    ll ans = 0LL;

    for (int i = 1; i < N; i++)
    {
        if (v == B[i])
        {
            cnt++;
        }
        else
        {
            ans += (cnt * (cnt - 1)) / 2;

            v = B[i];
            cnt = v == 0 ? 2 : 1;
        }
    }

    ans += (cnt * (cnt - 1)) / 2;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;
const int MAX_V = 200010;

struct edge{
   int to, cost;
   edge(int to, int cost):to(to), cost(cost){}
};

vector<edge> G[MAX_V];

struct Dijkstra{
    vector<int> d, dp;
    Dijkstra(){}
    Dijkstra(int V){
        d.resize(V, INF);
        dp.resize(V, 0);
    }
    void calc(int s){
        d[s] = 0;
        dp[s] = 1;
        priority_queue<P, vector<P>, greater<P> > q;
        q.push(P(d[s], s));
        while(!q.empty()){
            P p = q.top(); q.pop();
            int from = p.second;
            int cost = p.first;
            if(d[from] < cost) continue;
            rep(i, 0, G[from].size()){
                int next = G[from][i].to;
                int newCost = cost + G[from][i].cost;
                if(d[next] > newCost){
                    d[next] = newCost;
                    dp[next] = dp[from];
                    q.push(P(newCost, next));
                }else if(d[next] == newCost){
                    dp[next] = (dp[next] + dp[from]) % mod;
                }
            }
        }
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    rep(i, 0, m){
        int s, t, d;
        cin >> s >> t >> d;
        G[s].push_back({t, d});
    }
    Dijkstra dstr(n);
    dstr.calc(s);
    rep(i, 0, n){
        int tmp = dstr.d[i];
        if(tmp == INF) cout << "INF" << endl;
        else cout << tmp << endl;
    }
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);

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

  vector<int> b(n, 0);

  for (int i = n-1; i >= 0; i--) {
    // sum := iを除くiの倍数のボールの数の和
    int sum = 0;
    for (int j = i; j < n; j += (i+1)) {
      sum += b[j];
    }
    b[i] = (sum + a[i]) % 2;
  }

  int m = count(b.begin(), b.end(), 1);
  cout << m << endl;

  if (m == 0) { return 0; }

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

  return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        long long a[n];
        long long sum = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        for (int i = 0; i < n; ++i) {
            if (a[i] * n <= sum) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}


Measured memory_bytes: 3224
n, m = map(int, input().split())

graph = [[] for _ in range(n)]


for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l - 1].append(( d,r - 1))
    graph[r - 1].append((-d,l - 1))

INF = float("inf")
dist = [-INF]*n

# 未探索ノードの距離を0とする
for n in range(n):
    if dist[n] != -INF:
        continue
    else:
        stack = [n]
        dist[n] = 0
        
    # stackが空になるまで探索を繰り返す
    while len(stack):
        cur = stack.pop()
        
        # ノードcurと隣り合う未探索ノードをstackに追加
        for cost, nex_node in graph[cur]:
            if dist[nex_node] != -INF:
                continue
            else:
                dist[nex_node] = dist[cur] + cost
                stack.append(nex_node)

def solve():
    for i in range(n):
        for d,node in graph[i]:
            if dist[node]-dist[i] != d:
                print("No")
                return 0
            
    print("Yes")
    return 0

solve()

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

typedef long long ll;

ll gcd(ll a, ll b){
return a != 0 ? gcd(b % a, a) : b;
}

int main() {
ll a, b;
while(cin >> a >> b)
cout << gcd(a, b) << " " << a / gcd(a, b) * b << endl;}

Measured memory_bytes: 3092
N, T = map(int,input().split())
c = []
t = []
for i in range(N):
  c_temp, t_temp = map(int,input().split())
  c.append(c_temp)
  t.append(t_temp)
  
ans = 10000
  
for i in range(N):
  if t[i] <= T:
    if c[i] < ans:
      ans = c[i]
      
if ans == 10000:
  print('TLE')
else:
  print(ans)

Measured memory_bytes: 9124
#include <iostream>
using namespace std;
int main()
{
    int num;
    cin >> num;
    
    int  box[100010]={};
    int oe = num%2;
    int current;

    for(int i=0;i<num;i++){
        cin >> current;
        if(current%2==oe){
            cout << "0" << endl;
            return 0;
        }
        if(current>=num){
            cout << "0" << endl;
            return 0;
        }
        box[current] ++;
        if(box[current]>2){
            cout << "0" << endl;
            return 0;
        }
    }

    if(box[0]>=2){
        cout << "0" << endl;
        return 0;
    }

    int ans = 1;

    for(int i=0;i<num/2;i++){
        ans *=2;
        ans %=1000000000+7;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
N, M, Q = map(int, input().split())		# 5 7 2

A=[]	# (l,r)をそのまま保持
B=[]	# (l,r,n) lからrまでの本数nを保持, B[l][r]=n

for i in range(N+1):
	a=[0]*(N+1)
	B.append(a)

for i in range(M):
	l, r = map(int, input().split())		# 5 7
	A.append( (l,r) )
	B[l][r]+=1

#print("A", A)
#print("B", B)

for iR in range(1,N+1):
	for iC in range(1,N+1):
		B[iR][iC] += B[iR][iC-1]

for iC in range(1,N+1):
	for iR in range(iC, 1, -1):
		B[iR-1][iC] += B[iR][iC]


#print("B", B)


for i in range(Q):
	p, q = map(int, input().split())		# 5 7
	
	print( B[p][q] )
	



Measured memory_bytes: 30008
#include<vector>
#include<climits>
#include<algorithm>
const int INF = INT_MAX;
const int NIL = -1;
class RangeMinimumQuery {
public:
  RangeMinimumQuery(int s) {
    size_ = 1;
    while(size_ < s) size_ <<= 1;
    node_ = std::vector<int>((size_ << 1) - 1, INF);
  }
  int find(int left, int right) const {
    return query(left, right, 0, 0, size_ - 1);
  }
  void update(int index, int value) {
    int i = index + size_ - 1;
    node_[i] = value;
    while((i = parent(i)) != NIL) node_[i] = std::min(node_[left_child(i)], node_[right_child(i)]);
  }
private:
  int parent(int node) const {return node == 0 ? NIL : (node - 1) >> 1;}
  int left_child(int node) const {return (node << 1) + 1;}
  int right_child(int node) const {return (node << 1) + 2;}
  int query(int a, int b, int k, int l, int r) const {
    if(b < l || r < a) return INF;
    if(a <= l && r <= b) return node_[k];
    int vl = query(a, b, left_child(k), l, (l + r) / 2);
    int vr = query(a, b, right_child(k), (l + r) / 2 + 1, r);
    return std::min(vl, vr);
  }
  int size_;
  std::vector<int> node_;
};

#include<bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  while(cin >> n >> m, n | m) {
    vector<int> scone(n);
    for(auto& i: scone) cin >> i;

    vector<int> sum = {0};
    for(auto i: scone) sum.push_back((sum.back() + (i % m)) % m);

    int answer = 0;
    RangeMinimumQuery rmq(m);
    for(int j = 0; j < sum.size(); ++j) {
      answer = max(answer, sum[j] - rmq.find(0, sum[j]));
      answer = max(answer, (sum[j] - rmq.find(sum[j] + 1, m) + m) % m);
      rmq.update(sum[j], sum[j]);
    }
    cout << answer << endl;
  }
}

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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define endl        "\n"
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a,b) 	for(int i=a;i<=b;i++)
#define IOS         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N=1e5 + 5;

int n,k;
string s;

string con(string ss, int l , int r)
{
	rep(i,l,r)
	{
		if(ss[i]=='R')
		{
			ss[i]='L';
		}
		else
		{
			ss[i]='R';
		}
	}
	return ss;
}

int check(string ss)
{
	int c=0;
	int ans=0;
	repp(i,0,n-1)
	{
		if(ss[i]!=ss[i+1])
		{
			ans += c;
			c=0;
		}
		else
		{
			c++;
		}
	}
	ans += c;
	return ans;
}

int checkR()
{
	int l= -1;
	int r= -1;
	string str = s;
	int kk=k;
	int i;
	for(i=0;i<n;i++)
	{
		if(kk==0)
		{
			break;
		}
		if(str[i]=='R' && l==-1)
		{
			continue;
		}
		else if(str[i]=='R' && kk>0 && l!=-1)
		{
			str = con(str,l,r);
			l=-1;
			r=-1;
			kk--;
		}
		else if(str[i]=='L' && l==-1)
		{
			l=i;
			r=i;
		}
		else
		{
			r++;
		}
	}
	if(l!=-1 && kk>0)
	{
		str = con(str,l,r);
	}
	return check(str);
}

int checkL()
{
	int l= -1;
	int r= -1;
	string str = s;
	int kk=k;
	int i;
	for(i=0;i<n;i++)
	{
		if(kk==0)
		{
			break;
		}
		if(str[i]=='L' && l==-1)
		{
			continue;
		}
		else if(str[i]=='L' && kk>0 && l!=-1)
		{
			str = con(str,l,r);
			l=-1;
			r=-1;
			kk--;
		}
		else if(str[i]=='R' && l==-1)
		{
			l=i;
			r=i;
		}
		else
		{
			r++;
		}
	}
	if(l!=-1 && kk>0)
	{
		str = con(str,l,r);
	}
	return check(str);
}

int checkRV()
{
	int l= -1;
	int r= -1;
	string str = s;
	reverse(all(str));
	int kk=k;
	int i;
	for(i=0;i<n;i++)
	{
		if(kk==0)
		{
			break;
		}
		if(str[i]=='R' && l==-1)
		{
			continue;
		}
		else if(str[i]=='R' && kk>0)
		{
			str = con(str,l,r);
			l=-1;
			r=-1;
			kk--;
		}
		else if(str[i]=='L' && l==-1)
		{
			l=i;
			r=i;
		}
		else
		{
			r++;
		}
	}
	if(l!=-1 && kk>0)
	{
		str = con(str,l,r);
	}
	return check(str);
}

int checkLV()
{
	int l= -1;
	int r= -1;
	string str = s;
	reverse(all(str));
	int kk=k;
	int i;
	for(i=0;i<n;i++)
	{
		if(kk==0)
		{
			break;
		}
		if(str[i]=='L' && l==-1)
		{
			continue;
		}
		else if(str[i]=='L' && kk>0)
		{
			str = con(str,l,r);
			l=-1;
			r=-1;
			kk--;
		}
		else if(str[i]=='R' && l==-1)
		{
			l=i;
			r=i;
		}
		else
		{
			r++;
		}
	}
	if(l!=-1 && kk>0)
	{
		str = con(str,l,r);
	}
	return check(str);
}

int32_t main()
{
	IOS;
	cin >> n >> k;
	cin >> s;
	cout << max({checkR(),checkRV(),checkL(),checkLV()}) << endl;
}


Measured memory_bytes: 648
#include<iostream>
#include<algorithm>
#include<cassert>
#include<map>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define N 100

const int INF = 1000100; 
int table[N];
int buycost[N];

int solve(int now,vector<int> *make){
  if ( table[now] != -1)return table[now];
  if(  make[now].size()==0)return table[now]=buycost[now];
  

  int ret = buycost[now],tmp=0;  
  rep(i,make[now].size()){
    tmp+=solve(make[now][i],make);
  }
  
  ret= min(ret,tmp);
  return table[now]=ret; 
}

main(){
  int n;
  while(cin>>n && n){
    map<string,int> M;
    rep(i,n){
      string t;int a;
      cin>>t>>a;
      M[t]=i;
      buycost[i]=a;
      table[i]=-1;
    }
    
    vector<int> make[n];
    cin>>n;
    rep(i,n){
      string a;
      cin>>a;
      int now =M[a],m;
      cin>>m;
      rep(j,m){
	cin>>a;
	make[now].push_back(M[a]);
      }     
    }
    string tmp;
    cin>>tmp;
    int tar=M[tmp];
    cout << solve(tar,make) << endl;
    
  }
  return false;
}

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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef struct data{
	int now;
	int cost;
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
int a,b,c,d, A[100], B[100], C[100][100], D[100][100][100];
string s, t, r;




int main(){
	cin >> a >> b >> c;
	d = 0;
	if(b == 1 && a == 10000) d += 10000;
	for(int i1 = 0; i1 <= 9; i1++){
		for(int i2 = 0; i2 <= 9; i2++){
			for(int i3 = 0; i3 <= 9; i3++){
				for(int i4 = 0; i4 <= 9; i4++){
					int check = i1+i2+i3+i4;
					int sum = i1*1000+i2*100+i3*10+i4;
					if(b <= check && check <= c && sum <= a){
						d += sum;
					}
				}
			}
		}
	}

	cout << d << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import Counter
N = int(input())
a = []
x = 2
while x ** 2 <= N:
    if N % x == 0:
        a.append(x)
        N /= x
        x = 2
    else:
        x += 1
else:
    if x <= N:
        a.append(int(N))

a = Counter(a)
ans = 0
for i in a:
    k = 1
    while True:
        if a[i] >= k:
            ans += 1
            a[i] -= k
            k += 1
        else:
            break

print(ans)

Measured memory_bytes: 9480
#include<stdio.h>
int main()
{
	int a[501][501], c[501], h = 0;
	int i, i2, n, m, x, y;
	while (1){
		for (i = 0; i < 501; i++){
			for (i2 = 0; i2 < 501; i2++){
				a[i][i2] = 0;
			}
			c[i] = 0;
		}
	
	h = 0;
	c[1] = 1;
	c[0] = 1;
	scanf("%d %d", &n, &m);
	if (n == 0 && m == 0)break;
	for (i = 0; i < m; i++){
		scanf("%d %d", &x, &y);
		a[x][y] = 1;
		a[y][x] = 1;

	}
	for (i = 1; i <= n; i++){
		if (a[1][i] == 1){
			if (c[i] == 0){
				h++;
			}
			c[i] = 1;
			for (i2 = 1; i2 <= n; i2++){
				if (a[i][i2] == 1 && c[i2] == 0){
					c[i2] = 1;
					h++;
				}
			}
		}
	}
	printf("%d\n", h);
}
return 0;
}

Measured memory_bytes: 2008
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e18

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0] + list(itertools.accumulate(a))
    c = [[0] * (n + 1) for i in range(n)]
    def f(l, r):
        tmp = inf
        if c[l][r]: return dp[l][r]
        c[l][r] = 1
        # print(dp, l, r)
        if l + 1 == r: return 0
        
        
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) + acc[r] - acc[l])
        # print(l,r)
        dp[l][r] = tmp
        return tmp
    print(f(0, n))
    # print(dp)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 45164
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;

bool valid(char c) {
    return '0' <= c && c <= '9';
}

int main() {
    vector<string> M;
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < H; ++i) {
        string s;
        cin >> s;
        M.push_back(s);
    }
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            if (M[h][w] == '.') {
                M[h][w] = '0';
            }
        }
    }
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            if (M[h][w] == '#') {
                if (h > 0 && w > 0 && valid(M[h-1][w-1]))
                    M[h-1][w-1] += 1;
                if (h > 0 && valid(M[h-1][w]))
                    M[h-1][w] += 1;
                if (h > 0 && w + 1 < W && valid(M[h-1][w+1]))
                    M[h-1][w+1] += 1;
                if (w > 0 && valid(M[h][w-1]))
                    M[h][w-1] += 1;
                if (w + 1 < W && valid(M[h][w+1]))
                    M[h][w+1] += 1;
                if (h + 1 < H && w > 0 && valid(M[h+1][w-1]))
                    M[h+1][w-1] += 1;
                if (h + 1 < H && valid(M[h+1][w]))
                    M[h+1][w] += 1;
                if (h + 1 < H && w + 1 < W && valid(M[h+1][w+1]))
                    M[h+1][w+1] += 1;
            }
        }
    }
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            cout << M[h][w];
        }
        cout << endl;
    }
}


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

const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main()
{
    ll n, k;
    cin >> n >> k;
    n%=k;
    cout<<min(n,k-n)<<endl;
}


Measured memory_bytes: 3600
n, k, q = map(int, input().split())
score_list = [k-q for _ in range(n)]
for i in range(q):
    tmp = int(input())
    score_list[tmp - 1] = score_list[tmp - 1] + 1

for j in score_list:
    if j > 0:
        print("Yes")
    else:
        print("No")


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

int main(void) {
  int N;
  cin >> N;
  vector<long long> A(N);
  int cnt = 0;
  long long sum = 0;
  long long minimum = LONG_LONG_MAX;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    cnt += (A[i] < 0 ? 1 : 0);
    sum += abs(A[i]);
    minimum = min(abs(A[i]), minimum);
  }
  cout << (cnt % 2 == 0 ? sum : sum - 2 * minimum) << endl;
  return 0;
}

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

#define int long long
#define uint unsigned int
#define pii pair<int, int>
#define fi first
#define se second

#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 REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())

#define PF(a) push_front(a)
#define PB(a) push_back(a)
#define EMPF(...) emplace_front(__VA_ARGS__)
#define EMPB(...) emplace_back(__VA_ARGS__)
#define EMP(...) emplace(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)

#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, -1, sizeof(a))

#define PW(n) (1LL << (n))
#define NUM(x) char(x + '0')
#define ALP(x) char(x + 'a')

using namespace std;

template <class T> inline bool CHMIN(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool CHMAX(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> void SORT(vector<T> &a) { sort(a.begin(), a.end()); }
template <class T> void SORTR(vector<T> &a) { sort(a.rbegin(), a.rend()); }
template <class T> void UNIQUE(vector<T> &a) { a.erase(unique(a.begin(), a.end()), a.end()); }

template <class S, class T> ostream& operator << (ostream& os, const pair<S, T> v) {
  os << "(" << v.first << ", " << v.second << ")"; return os;
}

const int MOD = 1000000007;
const int INF = 1LL << 50;
const double EPS = 1e-10;

/* ---------------------------------------------------------------------------------------------------- */

int A, B, Q;
int s[100010], t[100010];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> A >> B >> Q;
  s[0] = t[0] = -INF;
  s[A+1] = t[B+1] = INF;
  REP(i, A) cin >> s[i+1];
  REP(i, B) cin >> t[i+1];
  REP(i, Q) {
    int x; cin >> x;
    int p = lower_bound(s, s+A+2, x) - s;
    int q = lower_bound(t, t+B+2, x) - t;
    int L1 = x - s[p-1], L2 = x - t[q-1];
    int R1 = s[p] - x, R2 = t[q] - x;
    int ans = INF;
    CHMIN(ans, max(L1, L2));
    CHMIN(ans, max(R1, R2));
    CHMIN(ans, 2*L1+R2);
    CHMIN(ans, L1+2*R2);
    CHMIN(ans, 2*L2+R1);
    CHMIN(ans, L2+2*R1);
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 2944
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		double x = 0;
		int y = 0;

		if(n-m>0){
			y = (n-m)*100;
		}
		double k = Math.pow(2, m);

		double p,q;
		p=1-1/k;
		for(int i=1; i<3500000; i++){
			q=Math.pow(p, i-1);
			x += (y + 1900*m)*i*q/(double)k;
		}
		System.out.println(Math.round(x));
		sc.close();

	}
}


Measured memory_bytes: 21972
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
#include <string>
#include <climits>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
    map<int,int>arr;
    int n,x;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>x;
        arr[x]++;
    }
    int a = -1;
    for(map<int,int>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++){
        if(it->second >= 4){
            if(a == -1)cout<<1LL*(it->first)*(it->first)<<endl;
            else cout<<1LL*a*(it->first)<<endl;
            return 0;
        }else if(it->second >= 2){
            if(a == -1){
                a = it->first;
            }else{
                cout<<1LL*a*(it->first)<<endl;
                return 0;
            }
        }
    }
    cout<<0<<endl;
}


Measured memory_bytes: 4992
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
from collections import Counter
cntr = Counter(A)
ans = sum(A)
for b, c in Query:
    if cntr.get(b) == None:
        print(ans)
        continue
    diff = (c - b) * cntr[b]
    ans += diff
    print(ans)
    cntr[c] += cntr[b]
    cntr[b] = 0

Measured memory_bytes: 99372