akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
 
int main(){
  char c[1201];
  int i;
  int ans[26];
  int b=1;
  for(i=0; i<26; i++)ans[i]=0;
  i=0;
  while(scanf("%c",&c[i])!=EOF){
      if(c[i]>='a'&&c[i]<='z')ans[c[i]-'a']++;
      if(c[i]>='A'&&c[i]<='Z')ans[c[i]-'A']++;
      i+=1;
  }
  for(i=0; i<26; i++)printf("%c : %d\n",'a'+i,ans[i]);
  return 0;
}


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


int main(){
    long long N;
    cin >>N;
    long long sum = 0;
    for(int i=1;i<=N;i++){
        if(i%3==0||i%5 ==0) continue;
        else sum += i;
    }
    cout <<sum<<endl;

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
typedef long long int64;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> v[10];
    for (int i = 0; s[i]; ++ i) {
        v[s[i] - '0'].emplace_back(i);
    }
    int cnt = 0;
    for (int i = 0; i < 10; ++ i) {
        auto a = upper_bound(v[i].begin(), v[i].end(), -1);
        if (a == v[i].end()) continue;
        for (int j = 0; j < 10; ++ j) {
            auto b = upper_bound(v[j].begin(), v[j].end(), *a);
            if (b == v[j].end()) continue;
            for (int k = 0; k < 10; ++ k) {
                auto c = upper_bound(v[k].begin(), v[k].end(), *b);
                if (c == v[k].end()) continue;
                cnt ++;
            }
        }
    }
    cout << cnt;
}

Measured memory_bytes: 512
N, T = map(int, input().split())
min_cost = int(1e9)+11
flg = False
for i in range(N):
    c, t = map(int, input().split())
    if t <= T:
        flg = True
        min_cost = min(min_cost, c)
if flg:
    print(min_cost)
else:
    print("TLE")

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;

vector<double> t;
vector<double> v;
vector<double> t_sum;
double ans;

int main() {
    int N; cin >> N;
    t.assign(N,0);
    v.assign(N,0);
    t_sum.assign(N+1,0);
    REP(i,N) cin >> t[i];
    REP(i,N) cin >> v[i];

    REP(i,N) t_sum[i+1] += t_sum[i] + t[i];
    ans = 0.0;

    vector<double> dx;

    for(double x = 0.0; x<=t_sum[N]; x+=0.5){
        int itr = upper_bound(ALL(t_sum), x) - t_sum.begin()-1;
        double num = INF;
        REP(i,N){
            if(i<itr){
                num = min(num, v[i]-t_sum[i+1]+x);
            }else if(i==itr){
                num = min(num, v[i]);
            }else{
                num = min(num, v[i]+t_sum[i]-x);
            }
            num = min(num, x);
            num = min(num, t_sum[N]-x);
        }
        dx.push_back(num);
    }

    REP(d,dx.size()-1){
        ans += (dx[d] + dx[d+1])/4.0;
    }
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll Mod = 1000000007;
ll INF = Mod * 1145140;
int n,m,s,t;
vector<P> G1[114514];
vector<P> G2[114514];
ll D1[114514];
ll D2[114514];

// sから各頂点の距離　円
// tから各頂点の距離　スヌーク
void dijkstra() {
  priority_queue<P, vector<P>, greater<P>> Q;
  Q.push(make_pair(0,s));
  while (!Q.empty()) {
    P p = Q.top();
    Q.pop();
    if (D1[p.S] <= p.F) {
      continue;
    } else {
      D1[p.S] = p.F;
    }
    for (int i = 0; i < (int)G1[p.S].size(); i++) {
      if (p.F + G1[p.S][i].S < D1[G1[p.S][i].F]) {
        Q.push(make_pair(p.F + G1[p.S][i].S,G1[p.S][i].F));
      }
    }
  }
  Q.push(make_pair(0,t));
  while (!Q.empty()) {
    P p = Q.top();
    Q.pop();
    if (D2[p.S] <= p.F) {
      continue;
    } else {
      D2[p.S] = p.F;
    }
    for (int i = 0; i < (int)G2[p.S].size(); i++) {
      if (p.F + G2[p.S][i].S < D2[G2[p.S][i].F]) {
        Q.push(make_pair(p.F + G2[p.S][i].S,G2[p.S][i].F));
      }
    }
  }
}

int main() {
  cin >> n >> m >> s >> t;
  vector<ll> ans(n);
  s--; t--;
  for (int i = 0; i < m; i++) {
    int u,v;
    cin >> u >> v;
    u--; v--;
    ll a,b;
    cin >> a >> b;
    G1[u].emplace_back(v,a);
    G1[v].emplace_back(u,a);
    G2[u].emplace_back(v,b);
    G2[v].emplace_back(u,b);
  }

  for (int i = 0; i < n; i++) {
    D1[i] = INF;
    D2[i] = INF;
  }

  dijkstra();

  ans[n-1] = 1e15 - (D1[n-1] + D2[n-1]);

  for (int i = n-2; i >= 0; i--) {
    ll res = 1e15 - (D1[i] + D2[i]);
    ans[i] = max(ans[i+1],res);
  }

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

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

int main(void)
{
    int k, a, b;
    cin >> k >> a >> b;
    
    for(int i=a;i<=b;i++){
        if(i%k==0){
          cout << "OK" << endl;
          return 0;
        } 
    }

    cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define mod 1000000007
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper)
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
void make_unique(vector<ll> vec)
{
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
}


int main() 
{   ios;
    int t=1;
    //cin>>t;
    //cin.ignore(numeric_limits<streamsize>::max(),'\n');
    while(t--)
    {ll sum=0,ans=0,x,y,k,h,a,c,n,t,m,i,j,flag=0,count=0,moves=0;
     string s;
     cin>>s;
     
     if(s=="RRS"||s=="SRR")
     cout<<2<<endl;
     else if(s=="RSS"||s=="RSR"||s=="SRS"||s=="SSR")
     cout<<1<<endl;
     else if(s=="RRR")
     cout<<3<<endl;
     else 
     cout<<0<<endl;

     
     
    }
	return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <locale>
#include <iomanip>
#include <cstring>

#define nl '\n'

using namespace std;

int a, b;
string x, y;

int main(){
    cin >> a >> b;

    x = string(b, a +'0');
    y = string(a, b +'0');

    if (x < y) { 
        cout << x;
        return 0;
    }

    cout << y;



}

//g++ -std=c++14 comp.cpp -o b; ./b.exe
//g++ -std=c++14 comp.cpp && ./a.out

Measured memory_bytes: 256
import math


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


q = int(input())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and (i+1) % 2 == 0 and is_prime((i+1)//2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])

#print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]-1], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])


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

vector<int>a;
void dfs(ll v){
    if(v<=1e9){
        a.push_back(v);
        dfs(10*v+3);
        dfs(10*v+5);
        dfs(10*v+7);
    }
}

int main(){
    int n;
    cin>>n;
    dfs(0);
    sort(a.begin(),a.end());
    int ans=0;
    rep(i,a.size()){
        string s=to_string(a[i]);
        bool x=false,y=false,z=false;
        rep(j,s.size()){
            if(s[j]=='3')x=true;
            if(s[j]=='5')y=true;
            if(s[j]=='7')z=true;
        }
        if(a[i]<=n&&x&&y&&z)ans++;
    }
    cout<<ans<<endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for(int i = 0;i < n ; i ++){
        cin >> d.at(i);
    }

    for(int i = 0;i < n-1;i ++){
        for(int j = i+1;j < n;j++){
            if(d.at(i) == d.at(j)){
                d.at(j) = 0;
            }
        }
    }

    int sum = 0;
    for(int i = 0;i < n; i ++){
        if(d.at(i) != 0){
            sum ++;
        }
    }
    cout << sum << endl;
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1000000007;

int main()
{
   ll h,w;
   cin >> h >> w;
   if(h%3==0||w%3==0)
   {
      cout<<0<<endl;
      return 0;
   }
   ll ans = min(h,w);
   for(ll i=1;i<h;i++)
   {
      ll foo = w*i;
      ll hoge = (h-i)*(w/2);
      ll poiu = w*h-foo-hoge;
      ll ma = max(foo,max(hoge,poiu));
      ll mi = min(foo,min(hoge,poiu));
      //cout<<ma<<';'<<mi<<','<<foo<<';'<<hoge<<endl;;
      ans = min(ans,ma-mi);
   }
   
   for(ll i=1;i<w;i++)
   {
      ll foo = h*i;
      ll hoge = (w-i)*(h/2);
       ll poiu = w*h-foo-hoge;
      ll ma = max(foo,max(hoge,poiu));
      ll mi = min(foo,min(hoge,poiu));
      ans = min(ans,ma-mi);
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int w = tx - sx, h = ty - sy;
	REP(i, h) cout << "U";
	REP(i, w) cout << "R";
	REP(i, h) cout << "D";
	REP(i, w) cout << "L";
	cout << "L";
	REP(i, h+1) cout << "U";
	REP(i, w+1) cout << "R";
	cout << "DR";
	REP(i, h+1) cout << "D";
	REP(i, w+1) cout << "L";
	cout << "U" << endl;
	return 0;
}

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

int N;
int A[100100], B[100100], C[100100];
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N+1) cin >> A[i];
    rep(i, N) cin >> B[i];
    rep(i, N+1) C[i] = A[i];
    rep(i, N) {
        if (C[i]>=B[i]) C[i] -= B[i];
        else {
            C[i+1] = max(0ll, C[i+1]-(B[i]-C[i]));
            C[i] = 0;
        }
    }
    int SA = 0;
    rep(i, N+1) SA += A[i];
    int SC = 0;
    rep(i, N+1) SC += C[i];
    cout << SA-SC << endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<list>
#include<cctype>
#include<utility>
#include<algorithm>
#include<cctype>
using namespace std;

int main()
{
	string key;
	cin >> key;
	transform(key.begin(),key.end(),key.begin(),::toupper);
	string s;
	int cnt = 0;
	while(cin >>s && s!="END_OF_TEXT"){
		transform(s.begin(),s.end(),s.begin(),::toupper);
		if(s==key)cnt++;
	}
	cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1196
N = int(input())
D = []

for i in range(N):
    D.append(list(map(int, input().split())))

for i in range(N-2):
    if D[i][0] == D[i][1] and D[i+1][0] == D[i+1][1] and D[i+2][0] == D[i+2][1]:
        print('Yes')
        exit()

print('No')

Measured memory_bytes: 9184
using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    static void Main()
    {
        var hw = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var array = new List<string>();
        for (int i = 0; i < hw[0]; i++)
        {
            array.Add(Console.ReadLine());
        }

        var markRow = new bool[hw[0]];
        var markCol = new bool[hw[1]];
        for (int row = 0; row < hw[0]; row++)
        {
            for (int col = 0; col < hw[1]; col++)
            {
                if (array[row][col] == '#')
                {
                    markRow[row] = true;
                    markCol[col] = true;
                }
            }
        }

        for (int row = 0; row < hw[0]; row++)
        {
            if (markRow[row])
            {
                for (int col = 0; col < hw[1]; col++)
                {
                    if (markCol[col])
                    {
                        Console.Write(array[row][col]);
                    }
                }

                Console.WriteLine();
            }
        }
    }
}


Measured memory_bytes: 13396
using System;

namespace AOJ0500
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string input = Console.ReadLine();
                int N = int.Parse(input);

                if (N == 0)
                {
                    break;
                }

                int Apoint = 0;
                int Bpoint = 0;
                int A = 0;
                int B = 0;

                for (int i = 0; i < N; i++)
                {
                    input = Console.ReadLine();
                    string[] num = input.Split(' ');
                    A = int.Parse(num[0]);
                    B = int.Parse(num[1]);

                    if (A > B)
                    {
                        Apoint += A + B;
                    }
                    else if (B > A)
                    {
                        Bpoint += A + B;
                    }
                    else {
                        Apoint += A;
                        Bpoint += B;
                    }

                }

                Console.WriteLine(Apoint + " " +Bpoint);
            }
        }
    }
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;

struct Edge{
  int to,cap,cost,rev;
  Edge(int to=0,int cap=0,int cost=0,int rev=0):to(to),cap(cap),cost(cost),rev(rev){}
};

const int MAX_V = 1100, IINF = INT_MAX;
int V;
vector<Edge> G[MAX_V];
int h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V];

inline void add_edge(int from,int to,int cap,int cost){
  G[from].push_back(Edge(to,cap,cost,G[to].size()));
  G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int s,int t){
  int res = 0;
  fill(h,h+V,0);
  while(1){
    priority_queue<ii,vector<ii>,greater<ii> > Q;
    fill(dist,dist+V,IINF);
    dist[s] = 0;
    Q.push(ii(0,s));
    while(!Q.empty()){
      ii p = Q.top(); Q.pop();
      int v = p.second;
      if( dist[v] < p.first ) continue;
      for(int i=0;i<G[v].size();i++){
        Edge &e = G[v][i];
        if( e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to] ) { 
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          Q.push(ii(dist[e.to],e.to));
        }
      }
    }
    rep(v,V) h[v] += dist[v];
    if( h[t] >= 0 ) break;
    int d = IINF;
    for(int v=t;v!=s;v=prevv[v]) d = min(d,G[prevv[v]][preve[v]].cap);
    res += d * h[t];
    for(int v=t;v!=s;v=prevv[v]){
      Edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}


struct Data { int bitmask,cost; };
int n[2],arr[2][20];
#define pow2(a) ((a)*(a))

int main(){
  while( cin >> n[0] >> n[1], n[0]|n[1] ){
    rep(i,2) rep(j,n[i]) cin >> arr[i][j];
    int source = n[0] + n[1];
    int sink   = source + 1;
    V = sink+1;
    rep(i,V) G[i].clear();
    rep(i,n[0]) add_edge(source,i,1,0);
    rep(i,n[1]) add_edge(n[0]+i,sink,1,0);
    rep(i,n[0]) rep(j,n[1]) {
      int s = i, t = n[0] + j;
      int const_v = abs(arr[0][i]-arr[1][j]);
      add_edge(s,t,1,-const_v*pow2(const_v-30));
    }
    cout << -min_cost_flow(source,sink) << endl;
  }
  return 0;
}

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

int n;
int w[101];

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

    for(int i = 0; i < n - 1; ++i){
        w[i+1] += w[i];
    }

    int ans = 1e8;
    for(int i = 0; i < n - 1; ++i){
        int diff = abs(w[i] - (w[n-1] - w[i])); 
        if(ans > diff) {
            ans = diff;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
struct dian
{
    long long x;
    int id;
}a[2010];
bool cmp(const dian &x,const dian &y)
{
     return x.x>y.x;
}
long long f[2010][2010],ans;
int main()
{
     int i,j;
     cin>>n;
     for(i=1;i<=n;i++) 
     {
         cin>>a[i].x;
         a[i].id=i;
     }
     sort(a+1,a+n+1,cmp);
     for(i=1;i<=n;i++)
      for(j=0;j<=i;j++)
      {
          if(j==0) f[i][j]=f[i-1][j]+a[i].x*abs(a[i].id-(n-i+j+1));
          else if(j==i) f[i][j]=f[i-1][j-1]+a[i].x*abs(a[i].id-j);
          else
          f[i][j]=max(f[i-1][j-1]+a[i].x*abs(a[i].id-j),f[i-1][j]+a[i].x*abs(a[i].id-(n-i+j+1)));
      }
     for(i=0;i<=n;i++) if(f[n][i]>ans) ans=f[n][i];
     //cout<<f[1][1]<<" "<<f[1][0]<<endl;
     cout<<ans;
     cin>>i;
}
          
     
     


Measured memory_bytes: 26316
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long long ll;

template <typename T> void max_self(T& a, T b){
	a = max(a,b);
}

void solve(){	
    ll n,k;
    cin>>n>>k;
    ll ans = n%k;
    if( abs(ans-k) < ans){
		ans = abs(ans-k);
	}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    //int t; cin >> t;
    //while(t--) solve();
    //
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    int a, b;
    cin >> a >> b;

    int ans = 0;
    int tmp = 1;
    while(tmp < b) {
        tmp += a-1;
        ans++;
    }

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

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

using namespace std;

const int N = 2e5 + 5;

int n, m, deg[N][2];
vector <int> g[N], same;
string s;
bool in[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s; memset(in, 0, sizeof(in)); s = "#" + s;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u][s[v] - 'A']++; deg[v][s[u] - 'A']++;
    }

    for (int i = 1; i <= n; i++) {
        if (!deg[i][0] || !deg[i][1]) {
            in[i] = true;
            same.push_back(i);
        }
    }

    for (int i = 0; i < same.size(); i++) {
        int u = same[i];
        for (int v: g[u]) {
            deg[v][s[u] - 'A']--;
            if (!deg[v][0] || !deg[v][1]) {
                if (!in[v]) {
                    in[v] = true;
                    same.push_back(v);
                }
            }
        }
    }

    if (same.size() != n) cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 13456
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
using namespace std;

int main(){
    int n,a;
    string s;
    cin>>n>>s;
    a=s.size();
    if(a<=n){
        cout<<s<<endl;
    }
    else{
        s[n]='.';
        s[n+1]='.';
        s[n+2]='.';
        for(int i=0;i<n+3;i++){
            cout<<s[i]<<flush;
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3600
#include <iostream>

using namespace std;

int main()
{
    int K, S;

    cin >> K >> S;

    int ans = 0;

    for (int X = 0; X <= K; X++)
    {
        for (int Y = 0; Y <= K; Y++)
        {
            int Z = S - X - Y;

            if (0 <= Z && Z <= K)
            {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

#define IL __inline__ __attribute__((always_inline))

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++ i)
#define FOR(i, a, b) for (int i = a, i##end = b; i < i##end; ++ i)
#define Rep(i, a, b) for (int i = a, i##end = b; i >= i##end; -- i)
#define REP(i, a, b) for (int i = (a) - 1, i##end = b; i >= i##end; -- i)

typedef long long LL;

template <class T>
IL bool chkmax(T &a, const T &b) {
  return a < b ? ((a = b), 1) : 0;
}

template <class T>
IL bool chkmin(T &a, const T &b) {
  return a > b ? ((a = b), 1) : 0;
}

template <class T>
IL T mymax(const T &a, const T &b) {
  return a > b ? a : b;
}

template <class T>
IL T mymin(const T &a, const T &b) {
  return a < b ? a : b;
}

template <class T>
IL T myabs(const T &a) {
  return a > 0 ? a : -a;
}

const int INF = 0X3F3F3F3F;
const double EPS = 1E-10, PI = acos(-1.0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
/*------------------------------header------------------------------*/

const int MAXN = 100000 + 5;

int a[MAXN];

int main() {
  int n;
  scanf("%d", &n);
  LL answer = 0;
  For(i, 1, n) {
    scanf("%d", &a[i]);
    if (a[i - 1] && a[i]) {
      -- a[i - 1], -- a[i];
      ++ answer;
    }
    answer += a[i] >> 1;
    a[i] &= 1;
  }
  printf("%lld\n", answer);
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision() <<
using namespace std;
using ll = long long;

int main() {
    int n,k;
    string s,t,t2;
    cin>>s>>t;
    s+=t[t.length()-1];
    if(s==t)cout<<"Yes";
    else cout<<"No";
}

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

ll n, W; ll w[345678], v[345678], dp[502][123456];
void solve() {
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j <= W; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i + 1][j];
			}
			else {
				dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
			}
		}
	}
	return;
}

signed main() {
	cin >> n >> W;
	rep(i, n) {
		cin >> w[i] >> v[i];
	}
	solve();
	cout << dp[0][W] << endl;
	return 0;
}

Measured memory_bytes: 82112
def main(s):
  n=len(s)
  ans=0
  na=0
  i=0
  while i<n:
    if s[i]=='A':
      na+=1
      i+=1
    elif s[i]=='B' and i<n-1 and s[i+1]=='C' and na>0:
      ans+=na
      i+=2
    else:
      na=0
      i+=1
  print(ans)
if __name__=='__main__':
  s=list(input())
  main(s)
  

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

const int N = 111;

int n;
char ss[N];
//set<long long> dp[N];
vector<long long> dp[N];

long long value( int i, int j ) {
	long long rt = 0;
	for( int k = i; k <= j; k++ )
		rt = rt * 10 + ss[k] - '0';
	return rt;
}
int main() {
	scanf( "%s", ss + 1 );
	n = (int)strlen(ss + 1);
	dp[0].push_back( 0 );
	for( int i = 1; i <= n; i++ ) {
		for( int j = 1; j <= i; j++ ) {
			for( auto it = dp[j-1].begin(); it != dp[j-1].end(); ++it ) {
				dp[i].push_back( *it + value(j,i) );
			}
		}
	}
	long long ans = 0;
	for( auto it = dp[n].begin(); it != dp[n].end(); ++it ) {
		ans += *it;
//		printf( "%lld\n", *it );
	}
	printf( "%lld\n", ans );
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <numeric>
#include <queue>
#include <math.h>
using namespace std;
struct hash_pair {
	template <class T1, class T2>
	size_t operator()(const pair<T1, T2>& p) const
	{
		auto hash1 = hash<T1>{}(p.first);
		auto hash2 = hash<T2>{}(p.second);
		return hash1 ^ hash2;
	}
};
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

#define ff first
#define ss second 
#define pp pair
#define ULRED 1000000007
#define MS(x,y) x-y>0?x-y:y-x 
#define MAX(x,y) x>y?x:y
/*------------------------------------------------------------------*/

int main()
{
	FAST_IO
	ll n;
	cin >> n;
	vector<ll> h(n+1, 0);
	vector<ll> dp(n + 1,LLONG_MAX);
	for (ll i = 1; i < n + 1; i++)
		cin >> h[i];
	h[0] = LLONG_MAX;
	dp[0] = 0;
	dp[1] = 0;
	for (ll i = 2; i < n + 1; i++)
	{
		// Jump to N-1 and N-2;
		dp[i] = min(dp[i - 1] + (MS(h[i - 1], h[i])), dp[i - 2] + (MS(h[i - 2], h[i])));
	}
	cout << dp[n]<<endl;
}


Measured memory_bytes: 1792
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int t[101];
int pri[26];
int res = 0;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[y] = px;
	}
	else {
		pr[x] = py;
	}
	return true;
}
struct edge {
	int to;
	bool use = false;
	edge(int _to) : to(_to) {}
};

void solv() {

	int n, m, c;
	cin >> n >> m >> c;
	int b[25];
	for (size_t i = 0; i < m; i++)
	{
		cin >> b[i];
	}
	ll res = 0;
	for (size_t i = 0; i < n; i++)
	{
		ll v = 0;
		for (size_t j = 0; j < m; j++)
		{
			ll a;
			cin >> a;
			v += a * b[j];
		}
		if (v + c > 0) {
			res++;
		}
	}
	cout << res << endl;
}


int main() {
	solv();

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int Maxn=500,INF=1e9;
int ans,n,m,r,d[Maxn][Maxn],a[Maxn],b[Maxn];

void Check()
{
    int sum=0;
    for (int i=2; i<=r; i++) sum+=d[a[b[i-1]]][a[b[i]]];
    ans=min(ans,sum);
}

int main()
{
    for ( ; scanf("%d%d%d",&n,&m,&r)!=EOF; )
    {
        for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) d[i][j]=INF;
        for (int i=1; i<=r; i++) scanf("%d",&a[i]);
        for (int i=1; i<=m; i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            d[x][y]=min(d[x][y],z);
            d[y][x]=min(d[y][x],z);
        }
        for (int k=1; k<=n; k++)
        for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        ans=INF;
        for (int i=1; i<=r; i++) b[i]=i;
        Check();
        while (next_permutation(b+1,b+r+1))
        {
            Check();
        }
        printf("%d\n",ans);
    }
    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextLong();

  vector<int> ans(N+1);
  REP(i, N-1) {
    int a = nextLong();
    ans[a]++;
  }
  for (int i = 1; i <= N; i++) cout << ans[i] << '\n';
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 4036
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

a,b,c = map(int,readline().split())
k = int(readline())
ct = 0
while a >= b:
    b*= 2
    ct += 1

while b >= c:
    c *= 2
    ct += 1

if ct <= k:
    print("Yes")
else:
    print("No")


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a.at(i);
    }
    sort(a.rbegin(), a.rend());
    const vector<int> cost = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

    vector<int> max_digit(n + 1, -1);
    max_digit.at(0) = 0;
    for (int i = 0; i < n; i++) {
        if (max_digit.at(i) == -1) continue;
        
        for (int j = 0; j < m; j++) {
            int c = cost.at(a.at(j));
            if (i + c <= n) max_digit.at(i + c) = max(max_digit.at(i + c), max_digit.at(i) + 1);
        }
    }

    int num = n;
    string ans;
    int d = max_digit.at(n);
    
    while (num > 0) {
        for (int i = 0; i < m; i++) {
            int c = cost.at(a.at(i));
            if (num - c < 0) continue;
            
            if (d - 1 == max_digit.at(num - c)) {
                ans += to_string(a.at(i));
                num -= c;
                d--;
                break;
            }
        }
    }
    cout << ans << endl;
}  

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    A,B,T = map(int, lines.pop(0).split(' '))
    res = 0
    S = A
    while S < T + 0.5:
        res += B
        S += A
    print(res)
lines = [x.strip() for x in sys.stdin.readlines()]
solve(lines)

Measured memory_bytes: 3060
#include <iostream>
#include<algorithm>
#include <vector>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define max(x,y) (((x)>(y)) ? x:y)
#define min(x,y) (((x)<(y)) ? x:y)
#define FOR(a,b,c) for(b=(c);b<(a);b++)
#define ender {return 0;}
#define tosasuretu(a) (a*(a+1)/2)
inline ll kaizyo(ll);
ll gcd(ll, ll);
ll combination(ll, ll);
int main() {
	int n;
	cin >> n;
	if (n % 111 == 0) {
		cout << n;
		return 0;
	}
	n /= 111;
	n += 1;
	cout << n * 111;
	return 0;
}


inline ll kaizyo(ll x) {
	long ans = 1;
	for (int z = 0; z < x; z++) {
		ans *= (x - z);
	}
	return ans;
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

ll dp[61][2][2][2];
ll L, R;

ll dfs(int pos, bool ismax, bool ismin, bool zero) {
	if (pos == -1) return 1;
	ll &res = dp[pos][ismax][ismin][zero];
	if (~res) return res;
	
	res = 0;
	if (!ismax || ismax && R >> pos & 1) res += dfs(pos - 1, ismax, ismin & (L >> pos & 1), false);
	if (!ismin || ismin && L >> pos & 1 ^ 1) {
		if (!zero && (!ismax || ismax && R >> pos & 1)) res += dfs(pos - 1, ismax, ismin, zero);
		res += dfs(pos - 1, ismax & (R >> pos & 1 ^ 1), ismin, zero);
	}
	res %= MOD;
	return res;
}

int main() {
	cin >> L >> R;
	memset(dp, -1, sizeof(dp));
	cout << dfs(60, true, true, true) << endl;
	return 0;
}


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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 110000

int N;
int a[MAX];
int used[MAX];
int used2[MAX];

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int ans = 0;
	
	cin>>N;
	
	for(int i = 0; i < N; i++){
		cin>>a[i];
	}
	
	for(int i = 0; i < N; i++){
		if(used[i]) continue;
		int po = i;
		for(int j = 1; ;j++){
			// cout<<"j = "<<j<<" po = "<<po<<" "<<used2[po]<<endl;
			if(used2[po] == i+1){
				ans += j-used[po];
				break;
			}
			if(used[po]) break;
			used2[po] = i+1;
			used[po] = j;
			po += a[po];
			po %= N;
		}
	}
	// for(int i = 0; i < N; i++){
		// cout<<used[i]<<endl;
	// }
	cout<<ans<<endl;
	
	return 0;
}


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

int N = 4;
string s;

int main(){
  cin >> s;
  //char a0,a1,a2,a3;
  if(s[0] == s[1]){
    if(s[0] != s[2] && s[2] == s[3]) cout << "Yes" << endl;
    else cout << "No" << endl;
  }else{
    if((s[0]==s[2] && s[1]==s[3]) || (s[0]==s[3] && s[1]==s[2])) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  //for(int i = 0; i<N; i++){}
}

Measured memory_bytes: 256
import numpy as np
N = int(input())

x, y, h = np.array([list(map(int, input().split())) for i in range(N)]).T
"""
x = [0 for i in range(N)]
y = [0 for i in range(N)]
h = [0 for i in range(N)]
for i in range(N):
    x[i], y[i], h[i] = map(int, input().split())
"""
H = 0
Cx = 0
Cy = 0
Flag = True
for i in range(101):
    for j in range(101):
        Flag = True
        for k in range(N):
            if h[k] != 0:
                H = h[k] + abs(i - x[k]) + abs(j - y[k])
                break
        for k in range(N):
            if h[k] != max(H - abs(i - x[k]) - abs(j - y[k]), 0):
                Flag = False
                break
        
        if Flag:
            Cx, Cy = i, j
            break
    if Flag:
        break

print("{} {} {}".format(Cx, Cy, H))

Measured memory_bytes: 22232
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << '\n'
#define debug_arr(a , n) for(ll i = 0 ; i < n ; i++)cout << a[i] << " "
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<ll>
#define vll vector<ll> 
#define inf 1000000000
#define mod 1000000007

const ll max_n = 4e2 + 9;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a , ll b)
{
    ll prod = 1;
    while(b)
    {
        if(b&1)
        prod = (prod*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return prod;
}
ll n;
ll a[max_n] , sum[max_n];
ll dp[max_n][max_n];
ll fun(ll l , ll r){
    if(l == r)return 0;
    if(dp[l][r] != -1)return dp[l][r];
    ll &min1 = dp[l][r];
    min1 = fun(l , l) + fun(l + 1 , r) + (sum[l] - (l-1 >= 0 ? sum[l-1] : 0)) + (sum[r] - (l >= 0 ? sum[l] : 0));
    for(ll i = l+1 ; i < r ; i++){
        min1 = min(min1 , fun(l , i) + fun(i+1 , r) + (sum[i] - (l-1 >= 0 ? sum[l-1] : 0)) + (sum[r] - (i >= 0 ? sum[i] : 0)));
    }

    return min1;
}
int main()
{
    cin >> n;
    memset(dp , -1 , sizeof(dp));
    for(ll i = 0 ; i < n ; i++){
        cin >> a[i];
    }

    sum[0] = a[0];
    for(ll i = 1 ; i < n ; i++){
        sum[i] = sum[i-1] + a[i];
    }
    cout << fun(0 , n-1);
    return 0;
}

Measured memory_bytes: 1536
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
from operator import itemgetter

N = int(input())
l = []
for i in range(N):
    r = input().split()
    r.append(i + 1)      #並び替え前の番号をIDとして記録しておく
    l.append(r)

l.sort(key=lambda x:(x[0],-int(x[1])))

for i in range(N):
    print(l[i][2])

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

V<ll> divisor(ll n){
    V<ll> ret;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ret.push_back(i);
            if(i*i!=n)ret.push_back(n/i);
        }
    }
    sort(ret.begin(),ret.end());
    return ret;
}

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

bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(void){
    ll  A,B;
    int ans=0;
    cin>>A>>B;
    ll gcd_ab=gcd(A,B);
    V<ll> ab=divisor(gcd_ab);
    REP(i,ab.size()){
        if(IsPrime(ab[i])){
            ans++;
        }
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 384
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
const double PI = acos(-1);

int Par[100001];
int Rank[100001];
int id[100001];

bool flag;

void init(int n) {
	for (int i = 0; i < n; i++) {
		Par[i] = i;
		Rank[i] = 0;
		id[i] = -1;
	}
}

int find(int x) {
	if (Par[x] == x) {
		return x;
	}
	else {
		return Par[x] = find(Par[x]);
	}
}

void unite(int  x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (Rank[x]>Rank[y])swap(x, y);
	Par[x] = y;

	if (id[x] != -1 && id[y] != -1 && id[x] != id[y])flag = true;

	if (id[x] != -1) {
		id[y] = id[x];
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}


int main() {
	int n, m, k;
	cin >> n >> m >> k;
	init(n);
	int a, b, c;
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			unite(b, c);
			if (flag) {
				cout << i + 1 << endl;
				return 0;
			}
		}
		else if (a == 2) {
			b = find(b);
			if (id[b] != -1 && id[b] != c) {
				cout << i + 1 << endl;
				return 0;
			}
			id[b] = c;
		}
	}
	cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 4264
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
using namespace std;

int main(){

  string s;
  cin >> s;
  int a;
  int z;
  for(int i=0; i<s.size(); i++){
    if( s[i] == 'A' ){
      a = i;
      break;
    }
  }
  for(int i=s.size()-1; i>=0; i--){
    if( s[i] == 'Z' ){
      z = i;
      break;
    }
  }
  cout << z - a + 1 << endl;

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define REP(i, a, b) for(long long i=a; i<=b; ++i)
#define REPN(i, a, b) for(long long i=a; i<=b; --i)
#define rep(i, a, b) for(long long i=a; i<b; ++i)
#define rep0(i,b) for(long long i=0; i<b; ++i)
#define REP0(i,b) for(long long i=0; i<=b; ++i)
#include<cmath>
#include <iomanip>
using namespace std;


typedef long long ll;

int MODE = 1e9+7;
ll ans;


class Node
{
public:

    ll value;
    Node *next;


    Node(ll value)
    {
        this->value = value;
        next = nullptr;
    }
};


class LinkedList
{
public:
    Node *head = nullptr;
    Node *tail = nullptr;

    void insertAtTail(ll value)
    {
        Node *node = new Node(value);
        if(head == nullptr)
        {

            head = node;
            tail = node;
            return ;
        }
        else
        {
            tail->next = node;
            tail = node;
            return ;
        }

    }


    void show()
    {
        Node *temp = head;

        while(temp != nullptr)
        {
            cout<<temp->value<<" ";
            temp = temp->next;
        }
        cout<<endl;
    }


};





int main()
{

    int n;
    cin>>n;
    ll dp[n][n];
    memset(dp, -1, sizeof(dp));
    ll arr[n];
    rep0(i, n)
    {
        cin>>arr[i];
    }
    ll prefix[n+1];
    prefix[0] = 0;
    rep0(i, n+1)
    {
        prefix[i] = prefix[i-1] + arr[i];
    }
    for(int i=0; i<n; ++i)
    {
        dp[i][i] = 0;
    }


    for(int i=n-2; i>=0; --i)
    {

        for(int j=i+1; j<n; ++j)
        {
            dp[i][j] = 1e18+5;

            for(int k = i; k<j; ++k)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]);
            }
        }
    }


    /*for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            cout<<dp[i][j]<<"\t";
        }
        cout<<endl;
    }*/


    cout<<dp[0][n-1]<<endl;



    return 0;

}


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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;


int main(){
    string s;
    cin >> s;

    if(s == "keyence"){
        cout << "YES" << endl;
        return 0;
    }
    int n = s.size();
    rep(l, n){
        for(int r = l+1; r < n; r++){
            string str = s.substr(0, l) + s.substr(r);
            if(str == "keyence"){
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
    

    return 0;
}



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

int main() {
  int R,G,B,N;
  scanf("%d %d %d %d", &R,&G,&B,&N);

  vector<int> v{R,G,B};

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

  int one = N/v[2];
  int two = N/v[1];
  int count = 0;

  for(int i=0;i<one+1;++i){
    for(int j=0;j<two+1;++j){
      if((N-(i*v[2]+j*v[1]))%v[0] == 0 && i*v[2]+j*v[1]<=N){
        ++count;
      }
    }
  }

  cout << count << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

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

    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for(int i = 0; i < h; ++i)  cin >> s[i];

    int ans = 0;
    for(int sx = 0; sx < h; ++sx){
        for(int sy = 0; sy < w; ++sy){
            if(s[sx][sy] == '#')    continue;
            vector<vector<int>> dist(h, vector<int>(w, INF));
            queue<P> que;
            dist[sx][sy] = 0;
            que.push(P(sx, sy));
            while(!que.empty()){
                P p = que.front();
                que.pop();
                int x = p.first, y = p.second;
                for(int i = 0; i < 4; ++i){
                    int nx = x + dx[i], ny = y + dy[i];
                    if(nx < 0 || nx >= h || ny < 0 || ny >= w)  continue;
                    if(s[nx][ny] == '#')    continue;
                    if(dist[nx][ny] > dist[x][y] + 1){
                        dist[nx][ny] = dist[x][y] + 1;
                        que.push(P(nx, ny));
                    }
                }
            }
            for(int gx = 0; gx < h; ++gx){
                for(int gy = 0; gy < w; ++gy){
                    if(s[gx][gy] == '#')    continue;
                    chmax(ans, dist[gx][gy]);
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
A=list(map(int,input().split()))
Aminus=[]
Aplus=[]
negative=0
positive=0
posinega=0
for i in range(N):
    if A[i]>0:
        positive+=1
        Aplus.append(A[i])
    elif A[i]<0:
        negative+=1
        Aminus.append(A[i])
    else:
        posinega+=1
Aplus.sort()
Aminus.sort()
PLUS=positive*positive+negative*negative
MINUS=2*positive*negative
ZERO=N*N-PLUS-MINUS

PLUS=(PLUS-(N-posinega))//2
MINUS=MINUS//2
ZERO=(ZERO-posinega)//2
if K<=MINUS:
    #ans<0
    low=min(A)*max(A)
    high=0
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aminus[j]はjについて単調増加である。
                Aplus[i]*Aminus[low0]<mid<=Aplus[i]*Aminus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)
elif K<=MINUS+ZERO:
    print(0)
else:
    K-=MINUS+ZERO
    #ans>0
    low=0
    high=max(min(A)**2,max(A)**2)
    Aminus=Aminus[::-1]
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=positive
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aplus[j]はjについて単調増加である。
                Aplus[i]*Aplus[low0]<mid<=Aplus[i]*Aplus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aplus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aplus[i]*Aplus[i]<mid:
                tmp-=1
        for i in range(negative):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                if Aminus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aminus[i]*Aminus[i]<mid:
                tmp-=1
        tmp=tmp//2
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)


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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cerr << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cerr << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int n, d; cin >> n >> d;
  d *= d;
  int ans = 0;
  int x, y;
  REP(i,n) {
    cin >> x >> y;
    if(d >= x*x + y*y) {
      ++ans;
    }
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3592