akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>

int main(void){
char s[4906];
char p[1] = ".";
int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,si=0,j=0,k=0,l=0,m=0,n=0,o=0,cp=0,q=0,r=0,cs=0,t=0,u=0,v=0,w=0,x=0,y=0,z=0;
int len;


   while(scanf("%s",s) != EOF){
  len = strlen(s);
  for(int i = 0; i < len;i++) {
    if(s[i] == 'a'||s[i] == 'A'){
    a++;
    }
    else if(s[i] == 'b'||s[i] == 'B'){
    b++;
    }
    else if(s[i] == 'c'||s[i] == 'C'){
    c++;
    }
    else if(s[i] == 'd'||s[i] == 'D'){
    d++;
    }
    else if(s[i] == 'e'||s[i] == 'E'){
    e++;
    }
    else if(s[i] == 'f'||s[i] == 'F'){
    f++;
    }
    else if(s[i] == 'g'||s[i] == 'G'){
    g++;
    }
    else if(s[i] == 'h'||s[i] == 'H'){
    h++;
    }
    else if(s[i] == 'i'||s[i] == 'I'){
    si++;
    }
    if(s[i] == 'j'||s[i] == 'J'){
    j++;
    }
    else if(s[i] == 'k'||s[i] == 'K'){
    k++;
    }
    else if(s[i] == 'l'||s[i] == 'L'){
    l++;
    }
    else if(s[i] == 'm'||s[i] == 'M'){
    m++;
    }
    else if(s[i] == 'n'||s[i] == 'N'){
    n++;
    }
    else if(s[i] == 'o'||s[i] == 'O'){
    o++;
    }
    else if(s[i] == 'p'||s[i] == 'P'){
    cp++;
    }
    else if(s[i] == 'q'||s[i] == 'Q'){
    q++;
    }
    else if(s[i] == 'r'||s[i] == 'R'){
    r++;
    }
    else if(s[i] == 's'||s[i] == 'S'){
    cs++;
    }
    else if(s[i] == 't'||s[i] == 'T'){
    t++;
    }
    if(s[i] == 'u'||s[i] == 'U'){
    u++;
    }
    else if(s[i] == 'v'||s[i] == 'V'){
    v++;
    }
    else if(s[i] == 'w'||s[i] == 'W'){
    w++;
    }
    else if(s[i] == 'x'||s[i] == 'X'){
    x++;
    }
    else if(s[i] == 'y'||s[i] == 'Y'){
    y++;
    }
    else if(s[i] == 'z'||s[i] == 'Z'){
    z++;
    }
   
}
}

printf("a : %d\n",a);
printf("b : %d\n",b);
printf("c : %d\n",c);
printf("d : %d\n",d);
printf("e : %d\n",e);
printf("f : %d\n",f);
printf("g : %d\n",g);
printf("h : %d\n",h);
printf("i : %d\n",si);
printf("j : %d\n",j);
printf("k : %d\n",k);
printf("l : %d\n",l);
printf("m : %d\n",m);
printf("n : %d\n",n);
printf("o : %d\n",o);
printf("p : %d\n",cp);
printf("q : %d\n",q);
printf("r : %d\n",r);
printf("s : %d\n",cs);
printf("t : %d\n",t);
printf("u : %d\n",u);
printf("v : %d\n",v);
printf("w : %d\n",w);
printf("x : %d\n",x);
printf("y : %d\n",y);
printf("z : %d\n",z);

return 0;
}



Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    bool flag=true;
    if(s[0]!='A') flag=false;
    int ccnt=0;
    for(int i=2;i<=s.size()-2;++i){
        if(s[i]=='C') ++ccnt;
    }
    if(ccnt!=1) flag=false;
    else{
        int f=s.find("C");
        for(int i=1;i<s.size();++i){
            if(i!=f && (s[i]<'a' || s[i]>'z')) flag=false;
        }
    }
    if(flag) cout<<"AC"<<endl;
    else cout<<"WA"<<endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()

int K, X;

void solve() {
    FOR (x, X-K+1, X+K-1) {
        cout << x << " ";
    }
    cout << X+K-1 << endl;
}

int main() {
    cin >> K >> X;
    solve();
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n;
void dfs(string s,int cnt,char c){
  if(cnt==n)cout << s << endl;
  else for(char i='a';i<=c+1;i++)dfs(s+i,cnt+1,max(c,i));
}
int main(){
  cin >> n;
  dfs("a",1,'a');
}


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

using namespace std;
typedef pair<int, int> ii;

bool comp(pair<int, int> a, pair<int, int> b) {
    return a.first + a.second < b.first + b.second;
}
const long long INF = 1e18 + 2;

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

    ii arr[n];

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

    sort(arr, arr + n, comp);

    vector<long long> dp(n + 2,INF);
    dp[0] = 0;

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

    int ans = 1;
    for(int i = n; i >= 0; --i) {
        if(dp[i] < INF) {
            ans = i;
            break;
        }
    }
    cout << ans;


}

Measured memory_bytes: 384
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, S, E) for (int(X) = (S); (X) < (E); ++(X))
#define rrep(X, S, E) for (int(X) = (E)-1; (X) >= (S); --(X))
#define itrep(X, Y) for (auto(X) = (Y).begin(); (X) != (Y).end(); (X)++)
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll INF = 9 * 1e18;
const ll MOD = 1e9 + 7;

vector<long long> SieveOfEratosthenes(int max) {
  vector<long long> sieve;
  vector<long long> primes;

  for (int i = 1; i < max + 1; ++i) {
    sieve.push_back(i);
  }

  sieve[0] = 0;
  for (int i = 2; i < max + 1; ++i) {
    if (sieve[i - 1] != 0) {
      primes.push_back(sieve[i - 1]);
      for (int j = 2 * sieve[i - 1]; j < max + 1; j += sieve[i - 1]) {
        sieve[j - 1] = 0;
      }
    }
  }
  return primes;
}

void solve(long long N) {
  vl primes = SieveOfEratosthenes(55555);
  rep(i, 0, primes.size()) {
    if (primes[i] % 5 == 4) {
      cout << primes[i];
      N--;
      if (N != 0) {
        cout << " ";
      } else {
        cout << endl;
        return;
      }
    }
  }
}

int main() {
  long long N;
  scanf("%lld", &N);
  solve(N);
  return 0;
}


Measured memory_bytes: 892
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
int main(){
	ULL a=1,b=1,c,n;
	cin>>n;
	for (ULL i=1;i<=n;++i){
		c=a+b;
		a=b;
		b=c;
	}
	cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 3032
#include<iostream>
#include<algorithm>
#include<climits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
const int NMAX=1<<17;
int r,g;
int main(){
  cin>>r>>g;
  prin(2*g-r);
  

  return 0;
}


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

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));
    for (int len = 1; len <= N; len++) {
        for (int i = 0; i + len <= N; i++) {
            int j = i + len;
            if ((N - len) % 2 == 0)
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1]);
            else
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1]);
        }
    }
    cout << dp[0][N] << endl;
}

Measured memory_bytes: 70784
import math
t = input().split()
t = [int(i) for i in t]
r = math.sqrt(t[0]*t[0]+ t[1]*t[1])
h = t[2]
m = t[3]
if (h == 12):
    h = 0
if (m == 60):
    m = 0
hour_angle = 0.5 * (h * 60 + m) 
minute_angle = 6 * m 
angle = abs(hour_angle - minute_angle) 
angle = min(360 - angle, angle)
print(math.sqrt(r*r - 2*t[0]*t[1]*math.cos(angle*(2*math.pi/360))))

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

using int64 = long long;
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

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

int main() {
   int64 N, x;
   int64 a[111];
   cin >> N >> x;
   rep (i, N) {
      cin >> a[i];
   }
   sort(a, a+N);

   int64 ans = 0;
   rep (i, N) {
      x -= a[i];
      if (x < 0) break;
      if (i+1==N && x != 0) break;
      ans++;
   }
   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000007
int main(){
    int h,w,k; cin>>h>>w>>k;
    vector<vector<long>> dp(h+1,vector<long>(w,0));
    dp[0][0]=1;
    int num[]={1,2,3,5,8,13,21};
    for(int i=1;i<=h;i++){
        for(int j=0;j<w;j++){
            int l=j-1,r=w-1-(j+1);
            if(l<0)
                l=0;
            if(r<0)
                r=0;
            int n=num[r]*num[l];
            int a;
            if(j-2<0)
                a=num[r];
            else
                a=num[r]*num[j-2];
            int b;
            if(w-1-(j+2)<0)
                b=num[l];
            else
                b=num[l]*num[w-1-(j+2)];
            if(j-1>=0)
                dp[i][j-1]+=(dp[i-1][j]*a)%INF;
            if(j+1<w)
                dp[i][j+1]+=(dp[i-1][j]*b)%INF;
            dp[i][j]+=(dp[i-1][j]*n)%INF;
        }
    }
    cout<<dp[h][k-1]%INF;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <climits>
using namespace std;

bool comp(pair<int, string> a, pair<int, string> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % int(powl(10,9) + 7);
    }

    return f;
}

int main(){
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;

    int dx = tx - sx, dy = ty - sy;

    for(int i = 0; i < dx; i++){
        cout << 'R';
    }
    for(int i = 0; i < dy; ++i){
        cout << 'U';
    }
    for(int i = 0; i < dx; i++){
        cout << 'L';
    }
    for(int i = 0; i <= dy; ++i){
        cout << 'D';
    }
    for(int i = 0; i <= dx; ++i){
        cout << 'R';
    }
    for(int i = 0; i <= dy; ++i){
        cout << 'U';
    }
    cout << 'L' << 'U';
    for(int i = 0; i <= dx; ++i){
        cout << 'L';
    }
    for(int i = 0; i <= dy; ++i){
        cout << 'D';
    }
    cout << 'R' << endl;

    return 0;
}

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

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

const long long INF = 1e18;
//const ll mod = 1000000007;
ll H, W;
multiset<ll> st;
map<ll, ll> mp;

int main() {
    cin >> H >> W;
    ll L = 0;
    for(ll w = 0; w < W; w++) {
        mp[w] = 0;
        st.insert(0);
    }
    for(ll h = 0; h < H; h++) {
        ll A, B;
        cin >> A >> B;
        A--;
        ll minimum = INF;
        while(true) {
            auto itr = mp.lower_bound(A);
            if(itr == mp.end() or (*itr).first >= B) break;
            auto itr2 = st.lower_bound((*itr).second);
            st.erase(itr2);
            chmin(minimum, (*itr).second + B - (*itr).first);
            mp.erase(itr);
        }
        if(B < W and minimum != INF) {
            if(mp.count(B)) {
                auto itr = st.lower_bound(mp[B]);
                st.erase(itr);
                chmin(mp[B], minimum);
            } else {
                mp[B] = minimum;
            }
            st.insert(mp[B]);
        }
        if(st.size()) {
            cout << *(st.begin()) + h + 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 25496
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  int sum = 0;
  int a = 0, un = 0;
  bool flag = true;
  for (int i = 0; i < n; ++i)
  {
    string s;
    cin >> s;
    if (s == "A")
    {
      a++;
    }
    else
    {
      un++;
    }
    if (a < un)
      flag = false;
  }
  if (flag && a == un)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}



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

int main() { 
  int x, y;
  cin >> x >> y;
  int ans = 0;
  if (abs(x) <= abs(y)) {
    ans = abs(y) - abs(x);
    if ((x < 0 && y > 0) || (x >= 0 && y < 0)) ans++;
    if ((x < 0 && y < 0)) ans += 2;
  } else {
    ans = abs(x) - abs(y);
    if ((x > 0 && y <= 0) || (x < 0 && y > 0)) ans++;
    if (x > 0 && y > 0) ans += 2;
  }
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;

#define v(T) vector<T>
#define ttt(T) tuple<T, T, T>
#define pb push_back
#define mp make_pair
#define rep(i, s, n) for(int i=s;i<n;i++)
#define repeq(i,s,n) for(int i=s;i<=n;i++)
#define poiu(n) for(int i=0; i < n; i++)
#define MOD (int)10e9+7
#define endl '\n'

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

using namespace std;

int n;
int temp[3];
int dp[3][2];


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

    while(n--) {
        for(int i = 0;i<3;i++) cin >> temp[i], swap(dp[i][1],dp[i][0]);
        for(int i = 0; i<3; i++) {
            for(int j=1;j<3;j++)
                max_self(dp[i][1],dp[(i+j)%3][0]+temp[(i+j)%3]);
        }
    }

    int temp_max;
    for(int i = 0; i < 3; i++)
        max_self(temp_max, dp[i][1]);
    cout << temp_max;

    return 0;

}




Measured memory_bytes: 256
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    tel = [0] + il()

    # 初期位置
    position = 1

    # 移動回数がN回(町の数)以下の場合
    if K <= N:
        for k in range(K):
            position = tel[position]
        print(position)
        exit()

    # 移動回数がN回(町の数)以上の場合
    for n in range(N):
        position = tel[position]

    # 既にN回移動済みのため、
    # 必要な移動回数(K)から減算
    K -= N
    # ループまでに必要な移動回数を探索
    base = position
    cnt = 1
    while base != tel[position]:
        position = tel[position]
        cnt += 1

    # Kからループ数の余りを求め、
    # 余りの回数だけ移動を行う
    for k in range(K % cnt + 1):
        position = tel[position]
    print(position)


if __name__ == '__main__':
    main()


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

using namespace std;

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

template<class T>void byebye(T _rpl){cout<<_rpl<<endl;exit(0);}
int nextint(){int x;scanf("%d",&x);return x;}
ll nextll(){ll x;scanf("%lld",&x);return x;}

int M,D,ans;


int main(){
	scanf("%d%d",&M,&D);
	for(int m=1;m<=M;++m){
	for(int i=20;i<=D;++i){
		int tens=i/10;
		int one=i%10;
		if(one>=2&&tens*one==m)ans++;
	}}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int H, W, x[52][52], rx, ry, cx, cy, cd; int used[52][52];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; char d[5] = "v>^<";//Left->++ Right->--
int main() {
	for (int i = 0; i < 2704; i++)x[i / 52][i % 52] = 1;
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char c; cin >> c;
			if (c == '.')x[i][j] = 0;
			else if (c == '#')x[i][j] = 1;
			else if (c == 'G') { x[i][j] = 0; rx = i; ry = j; }
			else {
				x[i][j] = 0; cx = i; cy = j;
				for (int k = 0; k < 4; k++) { if (c == d[k])cd = k; }
			}
		}
	}
	int cnt = 0;
	while (true) {
		used[cx][cy] = 1; cnt++;
		if (cnt >= H*W * 2) { cout << "-1" << endl; return 0; }
		if (cx == rx && cy == ry)break;

		int fx = cx + dx[cd], fy = cy + dy[cd];
		if (x[fx][fy] == 1) { cd++; }
		else {
			int gx = cx + dx[(cd + 3) % 4], gy = cy + dy[(cd + 3) % 4];
			int hx = gx + dx[cd], hy = gy + dy[cd];
			if (x[hx][hy] == 1) { cx = fx; cy = fy; }
			else {
				cx = hx; cy = hy; cd--;
				used[fx][fy] = 1;
				if (fx == rx && fy == ry)break;
			}
		}
		if (cd >= 4)cd -= 4; if (cd < 0)cd += 4;
	}
	int ret = 0; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++)ret += used[i][j]; }
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 3084
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const ll INF=100000000000;
const ll MOD=1000000007;

int main()
{
 ll n, m, l;
 cin >> n >> m >> l;
 ll dis[n+1][n+1],disn[n+1][n+1];
 for(int i=0;i<n+1;i++){
   for(int j=0;j<n+1;j++){
     dis[i][j]=INF;
     disn[i][j]=INF;
   }
 }
 for(int i=1;i<n+1;i++) dis[i][i]=0;
 for(int i=0;i<m;i++){
   int a,b,c;
   cin >> a >> b >> c;
   dis[a][b]=c;
   dis[b][a]=c;
 }
  
  for (int k = 1; k < n+1; k++){
    for (int i = 1; i < n+1; i++){
      for (int j = 1; j < n+1; j++){
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
 
 for(int i=1;i<n+1;i++){
   for(int j=1;j<n+1;j++){
     if(dis[i][j]>l) disn[i][j]=INF;
     else if(dis[i][j]==0) disn[i][j]=0;
     else disn[i][j]=1;
   }
 }
  
 
  for (int k = 1; k < n+1; k++){
    for (int i = 1; i < n+1; i++){
      for (int j = 1; j < n+1; j++){
        disn[i][j] = min(disn[i][j], disn[i][k] + disn[k][j]);
      }
    }
  }
  
/*   for(int i=1;i<n+1;i++){
  for(int j=1;j<n+1;j++){
    cout << i << j << disn[i][j] << endl;
   }
 }*/
  
 int q;
 cin >> q;
 for(int i=0;i<q;i++){
   int s, t;
   cin >> s >> t;
   if(disn[s][t]>500) cout << -1 << endl;
   else cout << disn[s][t]-1 << endl;
 }

 return 0;
}

Measured memory_bytes: 1920
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
#define INF 0x7FFFFFFF
using namespace std;
int n,m;
int minl[MAXN],maxl[MAXN],p[MAXN];
bool flag=1;
vector<int> a[MAXN];
bool check(int x,int y,int val){
	if(y==INF)
		return 1;
	if(x>val||y<val)
		return 0;
	if((val-x)%2)
		return 0;
	return 1;
}
void dfs(int x,int f){
	for(int i=0;i<a[x].size();i++){
		int u=a[x][i];
		if(u==f)
			continue;
		dfs(u,x);
		if(minl[u]==-INF)
			continue;
		if(minl[x]==-INF){
			minl[x]=minl[u]-1;
			maxl[x]=maxl[u]+1;
		}
		else{
			if(maxl[x]%2==maxl[u]%2)
				flag=0;
			maxl[x]=min(maxl[x],maxl[u]+1);
			minl[x]=max(minl[x],minl[u]-1);	
		}
	}
	if(p[x]!=-1){
		if(check(minl[x],maxl[x],p[x])==0)
			flag=0;
		minl[x]=maxl[x]=p[x];
	}
}
void dfs1(int x,int f,int minv,int maxv){
	if(maxv!=INF){
		if(maxl[x]==INF){
			maxl[x]=maxv+1;
			minl[x]=minv-1;
		}
		else{
			if(maxv%2==maxl[x]%2)
				flag=0;
			if(p[x]!=-1){
				if(check(minl[x],maxl[x],p[x])==0)
					flag=0;
			}
			else{
				minl[x]=max(minl[x],minv-1);
				maxl[x]=min(maxl[x],maxv+1);
			}
		}
	}
	for(int i=0;i<a[x].size();i++){
		int u=a[x][i];
		if(u==f)
			continue;
		dfs1(u,x,minl[x],maxl[x]);
	}
	if(minl[x]>maxl[x])
		flag=0;
}

int main(){
	memset(p,-1,sizeof p);
	SF("%d",&n);
	for(int i=1;i<=n;i++){
		minl[i]=-INF;
		maxl[i]=INF;	
	}
	int u,v;
	for(int i=1;i<n;i++){
		SF("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	SF("%d",&m);
	for(int i=1;i<=m;i++){
		SF("%d%d",&u,&v);	
		p[u]=v;
	}
	dfs(1,0);
	dfs1(1,0,-INF,INF);
	if(flag){
		PF("Yes\n");
		for(int i=1;i<=n;i++)
			PF("%d\n",maxl[i]);
	}
	else{
		PF("No");
	}
}

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

const int mod = 1000000007;
int a[2000];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> a[i];
  
  long cnt = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (a[i] > a[j]) ++cnt;
    }
  }
  cnt = cnt * k % mod;
  
  long sub = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (a[i] == a[j]) continue;
      sub = (sub + (long(k) * (k - 1) / 2 % mod)) % mod;
    }
  }
  
  cout << (cnt + sub) % mod << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
using namespace std;
const int num1 = 1046527;
const int num2 = 13;
char c[num1][num2];
inline int getInt(char ch) {
	if (ch == 'A') return 1;
	else if (ch == 'C') return 2;
	else if (ch == 'G') return 3;
	else if (ch == 'T') return 4;
	return 0;
}
inline int getKey(char str[]) {
	int p = 1 ,sum = 0;
	for (int i = 0; i < strlen(str); i++) {
		sum += p*getInt(str[i]);
		p *= 5;
	}
	return sum;
}
int h1(char str[]) { return getKey(str) % num1;}
int h2(char str[]) { return 1 + getKey(str) % (num1 - 1); }
inline int insert(char str[]) {
	int i;
	for (i = 0; ; i++) {
		int h = (h1(str) + i*h2(str)) % num1;
		if (strcmp(c[h], str) == 0) return 0;//?????´??????return 0
		else if (strlen(c[h]) == 0) {
			strcpy(c[h], str);
			return 0;
		}
	}
	return 0;
}
inline int find(char str[]) {
	int i;
	int sum = 0;
	for (i = 0; sum < 104538; i++) {
		int h = (h1(str) + i*h2(str)) % num1;
		if (strcmp(c[h], str) == 0) return 1;
		else if (strlen(c[h]) == 0) return 0;
		sum++;
	}
	return 0;
}
int main() {
	int n;
	char com[7], str[num2];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> com >> str;
		if (com[0] == 'i')
			insert(str);
		else if (find(str))
			cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Measured memory_bytes: 16376
x,n = map(int,input().split())
p = [int(x) for x in input().split()]
all = list(range(102))
p_set = set(p)
p_all = set(all)
p_nokori = p_all - p_set
nokori = list(p_nokori)
import bisect
n = bisect.bisect_left(nokori,x)

left = x - nokori[n-1]
right = nokori[n] -x

if left <= right:
    print(nokori[n-1])
else:
    print(nokori[n])


Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}



template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WG = vector< Edges< T > >;
using UG = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;



template< typename T >
vector<T> dijkstra(WG<T> &g,int s){
  const auto lim = numeric_limits<T>::max();
  vector<T> dist(g.size(),lim);
  using Pi = pair<T,int>;
  priority_queue<Pi,vector<Pi>,greater<Pi>> q;
  dist[s] = 0;
  q.emplace(dist[s],s);
  while(!q.empty()){
    T cost;
    int idx;
    tie(cost,idx) = q.top();
    q.pop();
    if(dist[idx] < cost) continue;
    for( auto &e : g[idx]){
      auto next_cost = cost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      q.emplace(dist[e.to],e.to);
    }
  }
  return dist;
}


void f(int n,int m,int l){
  WG<int> es(n*(l+1));

  rep(i,m){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;
    FOR(j,c,l+1){
      es[a*(l+1)+j].PB(edge<int>(b*(l+1)+j-c,0));
      es[b*(l+1)+j].PB(edge<int>(a*(l+1)+j-c,0));
    }
    rep(j,l+1){
      es[a*(l+1)+j].PB(edge<int>(b*(l+1)+j,d));
      es[b*(l+1)+j].PB(edge<int>(a*(l+1)+j,d));
    }
  }

  vector<int> res=dijkstra(es,l);

  int ans=INF;
  rep(i,l+1){
    //cout<<' '<<res[(n-1)*(l+1)+i]<<endl;
    ans=min(ans,res[(n-1)*(l+1)+i]);
  }

  cout<<ans<<endl;
}



main(){
  int n,m,l;
  while(true){
    cin>>n>>m>>l;
    if(n==0) break;
    f(n,m,l);
  }

}



Measured memory_bytes: 19468
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W;
typedef long long ll;
typedef pair<ll, ll> Pa;

map<int, int> cnt;
int main() {
    cin >> N;
    rep(i, N){
        cin >> A;
        if(cnt.find(A) == cnt.end()) cnt[A] = 1;
        else cnt[A]++;
    }
    int ans = 0;
    for(auto itr = cnt.begin(); itr != cnt.end(); itr++){
        if((itr->second)%2 == 1) ans++;
    }
    cout << ans;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
#define INF 999999999
typedef long long ll;
using namespace std;
int main() {
    float a, b;
    cin >> a >> b;
    float x = (a+b)/2;
    cout << ceil(x) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                                                \
  ifstream in("atcoder-problems/code_festival_2017_qualc_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;

  vector<int> c(N);
  rep(i, N) { cin >> c[i]; }

  ll ans = pow(3, N);
  ll tmp = 1;
  rep(i, N) {
    if (c[i] % 2 == 0) {
      tmp *= 2;
    }
  }

  cout << ans - tmp << endl;
}

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //n个
		int[] arr1 = new int[n];
		for(int i=0;i<arr1.length;i++)
		{
			arr1[i]=sc.nextInt();
		}
		int q = sc.nextInt(); //q
		int[] arr2 = new int[q]; //不重复的
		for(int i=0;i<arr2.length;i++)
		{
			arr2[i]=sc.nextInt();
		}
		int sum=0;
		
		
		
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		
		for(int i=0;i<arr2.length;i++)
		{
			if(Arrays.binarySearch(arr1, arr2[i])>-1)
			{
				sum++;
			}
		}
		
		System.out.println(sum);
	}
}



Measured memory_bytes: 67956
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  ll n;
  cin>>n;
  vector<ll> a(n);
  
  int cl[111111]={};
  int cnt=0;
  vector<int> c;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(!cl[a[i]]){
	 cnt++;
	 c.pb(a[i]);
    }
    cl[a[i]]++;
  }
  if(cnt>=3){
    cout<<"No"<<endl;
    return 0;
  }
  
  if(cnt==1){
    if(a[0]<=n/2||a[0]==n-1)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
  }

  if(!cl[a[0]+1]&&!cl[a[0]-1]){
    cout<<"No"<<endl;
    return 0;
  }

  int sg=cl[min(c[0],c[1])];
  //dbg(sg);
  if(sg>=max(c[0],c[1])){
    cout<<"No"<<endl;
    return 0;
  }
  if((n-sg)/2>=max(c[0],c[1])-sg)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}


Measured memory_bytes: 2044
input_line = map(int, raw_input().split() )

W = input_line[0]
H = input_line[1]
x = input_line[2]
y = input_line[3]
r = input_line[4]

if( ((x-r)>=0)and((x+r)<=W)and((y+r)<=H)and((y-r)>=0) ):
	print 'Yes'
else:
	print  'No'

Measured memory_bytes: 6440
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    s=input()
    l=[]
    for i in s:
        if i=='0':
            l.append('0')
        elif i=='1':
            l.append('1')
        else:
            if len(l)>=1:
                l.pop(-1)
    ans=''
    for j in l:
        ans+=j
    print(ans)
resolve()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int k,n,l;
long long res,MOD=1000000007,p25[2000100];
long long inv[2000100],fac[2000100],ifac[2000100];
void init_math(int N){
	inv[1]=1LL;
	for(int i=2;i<=N;i++)
		inv[i]=(MOD-((MOD/i)*inv[MOD%i])%MOD);
	fac[0]=1LL;
	ifac[0]=1LL;
	for(int i=1;i<=N;i++){
		fac[i]=(fac[i-1]*(long long)(i))%MOD;
		ifac[i]=(ifac[i-1]*inv[i])%MOD;
	}
}
long long C(int x,int y){
	return ((fac[x]*ifac[y])%MOD*ifac[x-y])%MOD;
}
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>k>>s;
	n=s.size()+k;
	l=s.size();
	init_math(n);
	p25[0]=1;
	for(int x=1;x<=n;x++){
		p25[x]=(p25[x-1]*25LL)%MOD;
	}
	for(int x=l;x<=n;x++){
		res=(res+C(n,x)*p25[n-x]%MOD)%MOD;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 66740
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]
                
    def dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in range(n):
        right = t.search_higher(idx[i])
        left = t.search_lower(idx[i])
        ans+=(i+1)*(idx[i]-left)*(right-idx[i])
        t.insert(idx[i])
        #print(left,idx[i],right)
    print(ans)


main()


Measured memory_bytes: 120828
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;



const long double PI = 3.14159265359;
const int MAX_N = 100010;


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, Y; cin >> n >> Y;
	int x = -1, y = -1, z = -1;
	rep(i, n+1) {
		rep(j, n+1) {
			int k = n - i - j;
			if (0 <= k && k <= n && 10000 * i + 5000 * j + 1000 * k == Y) {
				x = i, y = j, z = k;
			}
		}
	}
	cout << x << " " << y << " " << z << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int area(int a, int b) {
  int x;
  x = a * b;
  return x;
}

int circum(int a, int b) {
  int y;
  y = 2*(a + b);
  return y;
}

int main(void) {
  int a, b;

  scanf("%d",&a); scanf("%d",&b);

  printf("%d %d\n", area(a, b), circum(a, b));
  
  return 0;
}



Measured memory_bytes: 2688
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
using namespace std;

typedef long long ll;

#define MOD 1000000007
#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

    double t, x;
    cin >> t >> x;

    printf("%.10f\n", (t / x));
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//ここまでテンプレ
int main(){
	string S;
	cin>>S;
	ll K;
	cin>>K;
	ll L=0;
	for(int i=0;i<S.length();i++){
		if(S[i]!='1')
			break;
		else
			L=i+1;
	}
	if(K<=L)
		cout<<1<<endl;
	else
		cout<<S[L]<<endl;
	return 0;
}

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

using namespace std;

#define inf 1001
#define min(a,b) (a < b ? a : b)

vector<int> h;

int cost(int l,int r){
    if(l == r){
        return h[l];
    }else if(l > r){
        return 0;
    }
    int res = 0;
    int flag = 1;
    int minnum = inf;
    for(int i=l;i<=r;i++){
        if(h[i] == 0){
            flag = 0;
            res += cost(l,i-1);
            res += cost(i+1,r);
            break;
        }else{
            minnum = min(minnum,h[i]);
        }
    }
    if(flag == 1){
        for(int i=l;i<=r;i++){
            h[i] -= minnum;
        }
        res = cost(l,r) + minnum;
    }
    return res;
}

int main(void){
    int n;
    cin >> n;
    int min = inf;
    for(int i=0;i<n;++i){
        int k;
        cin >> k;
        h.push_back(k);
    }
    cout << cost(0,n-1) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {

	int i, N;
	int count = 0;
	scanf("%d", &N);
	char S[50];

	scanf("%s", &S);
	for (i = 1; i < N; i++) {
		if (S[i - 1] == 'A' && S[i] == 'B' && S[i + 1] == 'C')
		{
			count++;
		}
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    cout << 800 * n - (n / 15) * 200 << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [0 for _ in range(M)]
for i in range(M):
    AB[i] = list(map(int, input().split()))

flg = [True for _ in range(N)]
for x in AB:
    if H[x[0] - 1] < H[x[1] - 1]:
        flg[x[0] - 1] = False
    elif H[x[0] - 1] > H[x[1] - 1]:
        flg[x[1] - 1] = False
    else:
        flg[x[0] - 1] = False
        flg[x[1] - 1] = False
print(flg.count(True))

Measured memory_bytes: 31944
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 998244353;
const int N = 3006;

int a[N], dp[N][N];

signed main(){
    IOS;
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        dp[i][a[i]] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s; j++) {
            if (j >= a[i]) dp[i][j] += dp[i-1][j] + dp[i-1][j-a[i]];
            else dp[i][j] += dp[i-1][j];
            dp[i][j] %= MOD;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dp[i][s];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 70784
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    for i in range(len(d)):
        for l in range(len(d)):
            for k in range(len(d)):
                d[l][k] = min(d[l][k], d[l][i] + d[i][k])
    return d


V, E = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(E)]
d = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    d[i][i] = 0
for i in std:
    d[i[0]][i[1]] = i[2]

ans = warshall_floyd(d)
for i in range(V):
    if ans[i][i] < 0:
        print("NEGATIVE CYCLE")
        sys.exit()
for i in range(V):
    for l in range(V):
        if ans[i][l] > 10 ** 11:
            ans[i][l] = "INF"
        else:
            ans[i][l] = str(ans[i][l])

for i in ans:
    print(" ".join(i))



Measured memory_bytes: 9108
a = int(input())
x = list(map(int,input().split()))
t = range(1,a+1)
A = []
B = []
for i in range(1,a+1):
    A.append(30000*i)
    B.append(30000*(a-i+1))
for i ,d in enumerate(x):
    A[d-1] -= a-i
print(*A)
print(*B)


Measured memory_bytes: 6344
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int key;
    Node *parent, *left, *right;
};
 
Node *root, *NIL;
 
void insert(int k)
{
    Node *y = NIL;
    Node *x = root;
    Node *z = new Node;
    z->key = k;
    z->left = NIL;
    z->right = NIL;
     
    while (x != NIL){
        y = x;
        if (z->key < x->key){
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
     
    z->parent = y;
    if (y == NIL){
        root = z;
    }
    else {
        if (z->key < y->key){
            y->left = z;
        }
        else {
            y->right = z;
        }
    }
}
 
void inorder(Node *u)
{
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}
 
void preorder(Node *u)
{
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}
 
Node *find(Node *u, int key)
{
    while (u != NIL && key != u->key){
        if (key < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        string com;
        cin >> com;
        if (com == "insert"){
            int x;
            scanf("%d", &x);
            insert(x);
        }
        else if (com == "find"){
            int x;
            scanf("%d", &x);
            if (find(root, x) != NIL) puts("yes");
            else puts("no");
        }
        else if (com == "print"){
            inorder(root);
            puts("");
            preorder(root);
            puts("");
        }
    }
     
    return 0;
}



Measured memory_bytes: 22024
#include <stdio.h>


int main(void)
{
	int sum = 0;
	int a, b;
	int digit = 0;
	
	while(scanf("%d %d", &a, &b) != EOF) {
		sum = a + b;
		while(sum){
			digit++;
			sum /= 10;
		}
		printf("%d\n", digit);
		digit = 0;
	}

	return 0;
}

Measured memory_bytes: 600
<?php
  
fscanf(STDIN,"%d",$n);
$x_li = explode(" ",trim(fgets(STDIN)));
$x_copy = $x_li;
sort($x_copy);
$defalut_center = $x_copy[($n+1)/2];
$spe_center = $x_copy[($n-1)/2];

foreach($x_li as $x){
if($x_copy[($n+1)/2]>$x){
  echo $defalut_center."\n";
}else{
  echo $spe_center."\n";
}
}




Measured memory_bytes: 33140
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	s := Scan()
	r := 0
	for _, v := range s {
		if string(v) == "R" {
			r++
		}
	}
	if r > n-r {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1772
#include <iostream>
#include <string>

int main()
{
	std::string S;
	std::cin >> S;

	long long ans = 0;
	long long n = 1 << (S.size() - 1);
	for (long long bits = 0; bits < n; ++bits) {
		long long sum = 0;
		long long cur = S[0] - '0';
		for (size_t i = 0; i < S.size() - 1; ++i) {
			if (bits & 1 << i) {
				sum += cur;
				cur = 0;
			}
			else
				cur *= 10;

			cur += S[i + 1] - '0';
		}
		sum += cur;
		ans += sum;
	}

	std::cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, y;
    cin >> x >> y;
    for(int a = 0; a <= x; ++a){
        int b = x - a;
        if(a * 2 + b * 4 == y){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
const lint MOD = pow(10, 9) + 7;



int main() {
	int N;
	cin >> N;
	vector<int>p(N);
	rep(i, N) {
		cin >> p[i];
	}
	int m = 1000000;
	int cnt = 0;
	rep(i, N) {
		m = min(m, p[i]);
		if (m == p[i]) {
			cnt++;
		}
	}
	cout << cnt << endl;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int[] f = new int[N+1];
	for (int i=2;i<=N;i++) {
	    for (int j=1;i*j<=N;j++) {
		f[i*j]++;
	    }
	}
	long count = 0;
	for (int i=1;i<=N;i++) {
	    count += (long)i * (long)(f[i]+1);
	}
	System.out.print(count);
    }
}


Measured memory_bytes: 74916