akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#define INF 1<<28
#define F first
#define S second
using namespace std;

int sx, sy, gx, gy;
typedef pair < int, int > P;
vector < P > p[5];
int memo[5][5][1111];

int solve(int k, P q){

  if(k == 4) return abs(p[q.F][q.S].F-gx) + abs(p[q.F][q.S].S-gy);
  if(memo[k][q.F][q.S]) return memo[k][q.F][q.S];

  int ans = INF, d = (q.F+1)%5, c;
  for(int i=0;i<p[d].size();i++){
    if(!k) c = abs(sx-p[d][i].F) + abs(sy-p[d][i].S);
    else c = abs(p[q.F][q.S].F-p[d][i].F) + abs(p[q.F][q.S].S-p[d][i].S);
    ans = min(ans, solve(k+1, P(d,i))+c);
  }

  return memo[k][q.F][q.S] = ans;
}

int main(){

  int w,h;
  char c;

  while(true){
    cin >> w >> h;
    if(!w && !h) break;

    for(int i=0;i<5;i++) p[i].clear();
    
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> c;
	if(c == 'S') sx = j, sy = i;
	if(c == 'G') gx = j, gy = i;
	else if(c != '.') p[c-'1'].push_back(P(j,i));
      }
    }
    
    P q = P(0,INF);
    for(int i=0;i<5;i++){
      memset(memo, 0, sizeof(memo));
      if(q.S > solve(0,P(i,0))) q.F = i+1, q.S = solve(0,P(i,0));
    }

    if(q.S == INF) cout << "NA\n";
    else cout << q.F << " " << q.S << endl;

  }
}

Measured memory_bytes: 1372
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>

#define SIZE 100005
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

using namespace std;


int main()
{	
	
	ll N;
	scanf("%lld", &N);
	ll sum=0;
	ll B[N+1];
	B[0]=100000;
	B[N]=100000;
	for(ll i=0;i<N-1;i++){
		scanf("%lld", &B[i+1]);
	}
	for(ll i=1;i<N+1;i++){
		sum+=min(B[i-1], B[i]);
	}

	printf("%lld", sum);
}


Measured memory_bytes: 128
import java.io.*;

class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br =
		new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		int num = Integer.parseInt(str);
		
		num = num*num*num;
		
		System.out.println(num);
	}
}

Measured memory_bytes: 24072
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main(){
    string s;
    cin >> s;
    for(int i=0;i<3;i++){
        if(s[i] == '1') s[i] = '9';
        else s[i] = '1';
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int len, target;
    cin >> len >> target;
    vector<int> arr(len);
    set<int> seen;
    bool match = false, big = false;
    for(int i = 0; i < len; i++) {
        cin >> arr[i];
        if(seen.count(target - arr[i])) {
            match = true;
        }
        if(arr[i] > target) {
            big = true;
        }
        if((match && big) || arr[i] == target) {
            cout << "POSSIBLE";
            return 0;
        }
        seen.insert(arr[i]);
    }
    cout << "IMPOSSIBLE";
}

Measured memory_bytes: 6644
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define double long double
int n;
double dp[400][400][400];

double dfs(int i, int j, int k)
{
  if(dp[i][j][k] != 0.0)
    return dp[i][j][k];
  
  if(i == 0 && j == 0 && k == 0)
    return 0.0;
  
  double ans = 0.0;
  if(i > 0)
    ans += (i*1.0/n) * (dfs(i-1, j, k) + 1.0);
  
  if(j > 0)
    ans += (j*1.0/n) * (dfs(i+1, j-1, k) + 1.0);
  
  if(k > 0)
    ans += (k*1.0/n) * (dfs(i, j+1, k-1) + 1.0);
  
  double t = (n-i-j-k)*1.0/n;
  
  ans += t;
  ans /= (1-t);
  
  return dp[i][j][k] = ans;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n;

  int t1 = 0, t2 = 0, t3 = 0;
  
  for(int i = 0, x; i < n; ++i)
  {
  	cin >> x;
    if(x == 1) ++t1;
    if(x == 2) ++t2;
    if(x == 3) ++t3;
  }
  
  cout << fixed << setprecision(15) << dfs(t1, t2, t3) << endl;
  
}


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

int main(){
    int a,b;
    cin>>a>>b;
    int B;
    B=b*10;
    int cnt=10;
    while(cnt>0){
        //cout<<B<<endl;
        if(B*8/100==a) {
            cout<<B<<endl;
            return 0;
        }
        B++;
        cnt--;
    }
    cout<<-1<<endl;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
  int n;
  cin >> n;
  string ans = n == 0 ? "0" : "";
  while(n != 0)
  {
    ans += (n % 2 == 0 ? '0' : '1');
    n -= (n % 2 == 0 ? 0 : 1);
    n /= -2;
  }
  reverse(ans.begin(), ans.end());
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=(int)(n);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
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;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    int N;
    cin>>N;
    vi A(N);
    cin>>A;
    sort(ALL(A));
    int sum=0;
    int t=0;
    REP(i,N) {
        sum+=A[i];
        if(i!=N-1 && 2*sum<A[i+1]) {
            t=i+1;
        }
    }
    cout<<N-t<<endl;
    return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

const ll INF = ((ll)1) << 60;
ll N,M,L,Q;

ll d[400][400]; // d[a][b]: 町a,b間の最短距離
ll f[400][400]; // d[a][b]: 町a,b間を最小補給回数

signed main() {
  rep(i,400) rep(j,400) { d[i][j]=INF; f[i][j]=INF; }

  cin >> N >> M >> L;
  rep(i,M){
    ll a,b,c;
    cin >> a >> b >> c;
    d[a][b] = c;
    d[b][a] = c;
  }

  // 各町間の最短距離を求める
  for (ll k=1; k<=N; k++) {
    for (ll i=1; i<=N; i++) {
      for (ll j=1; j<=N; j++) {
        d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
      }
    }
  }

  // 町間を補給回数1回でいけるかどうか
  for (ll i=1; i<=N; i++) {
    for (ll j=1; j<=N; j++) {
      if (d[i][j] <= L) {
        f[i][j] = 1;
        f[j][i] = 1;
      }
    }
  }

  // 各町間の最小補給回数を求める
  for (ll k=1; k<=N; k++) {
    for (ll i=1; i<=N; i++) {
      for (ll j=1; j<=N; j++) {
        f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
      }
    }
  }

  vector<ll> ans;
  cin >> Q;
  rep(i,Q) {
    ll a,b;
    cin >> a >> b;
    ll t = f[a][b];
    if (t == INF)
      ans.push_back(-1);
    else
      ans.push_back(t-1);
  }
  for (auto x: ans) {
    cout << x << endl;
  }
}


Measured memory_bytes: 3960
import sys

def solve():
    N, T = map(int, input().split())
    ts = list(map(int, input().split()))

    ans = T
    ans += sum(min(T, ts[i + 1] - ts[i]) for i in range(N - 1))

    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 26836
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4244) // 最悪をします
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <sstream>
#define BIT(nr) (1UL << (nr))
#define int long long
//#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
#define MIN -(9223372036854775807 / 2)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }


using namespace std;

//デバッグ用カッコの有無
#ifdef DEBUG
template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
	o << "{"; for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? ", " : "") << v[i]; o << "}"; return o;
}
#endif // DEBUG

template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
	for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? " " : "") << v[i]; return o;
}

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

int dxp[4] = { 0, 1 }; // x軸方向への変位(正のみ)
int dyp[4] = { 1, 0 }; // y軸方向への変位(負のみ)

using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;

	// libalgo のものに追加、メンバを追加するだけなので互換性は崩さないはず、逆辺のG[e.dstの]インデックスを保持
	int rev;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph& g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph& g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

int dp[110][110];
signed main() {
	int n;
	cin >> n;

	vector<int> ro(n), co(n);
	rep(i, n) {
		cin >> ro[i] >> co[i];
	}

	rep(i, 100) rep(j, 100) dp[i][j] = LL_HALFMAX;

	// [l, r) における最適解
	function<int(int, int)> rec = [&](int l, int r) -> int {
		if (dp[l][r] != LL_HALFMAX) {
			return dp[l][r];
		}
		
		if (r - l == 1) {
			return dp[l][r] = 0;
		}

		int ret = LL_HALFMAX;

		REP(m, l + 1, r) {
			int cand = ro[l] * ro[m] * co[r - 1] + rec(l, m) + rec(m, r);
			chmin(ret, cand);
		}

		return dp[l][r] = ret;
	};

	cout << rec(0, n) << "\n";
}



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

using namespace std;
 
int cnt_500(double f)
{
    if (f < 35.5) return 1;
    else if (f < 37.5) return 2;
    else if (f < 40) return 3;
    else if (f < 43) return 4;
    else if (f < 50) return 5;
    else if (f < 55) return 6;
    else if (f < 70) return 7; 
    return 8;
}
 
int cnt_1000(double t)
{
    if (t < 71) return 1;
    else if (t < 77) return 2;
    else if (t < 83) return 3;
    else if (t < 89) return 4;
    else if (t < 105) return 5;
    else if (t < 116) return 6;
    else if (t < 148) return 7;  
    return 8;
}
 
int main()
{
    double f, t;
    while (cin >> f >> t) {
        int grade = max(cnt_500(f), cnt_1000(t));
        switch (grade) { 
            case 1:
                cout << "AAA" << endl;
                break;
            case 2:
                cout << "AA" << endl;
                break;
            case 3:
                cout << 'A' << endl;
                break;
            case 4:
                cout << 'B' << endl;
                break;
            case 5:
                cout << 'C' << endl;
                break;
            case 6:
                cout << 'D' << endl;
                break;
            case 7:
                cout << 'E' << endl;
                break;
            case 8:
                cout << "NA" << endl;
                break;
        } 
    }
    return 0;
}

Measured memory_bytes: 3132
from collections import deque
import sys

input = sys.stdin.buffer.readline

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = B[::]
same = deque()
for i, (a, b) in enumerate(zip(A, B)):
    if a == b:
        if same and B[same[0]] != a:
            j = same.popleft()
            B[i], B[j] = B[j], B[i]
        else:
            same.append(i)
# print(A)
# print(B)
# print(same)
if same:
    s = A[same[0]]
    to_swap = []
    possible = False
    for i, (a, b) in enumerate(zip(A, B)):
        if a != s and b != s:
            to_swap.append(i)
        if len(to_swap) == len(same):
            possible = True
            break
    if not possible:
        print("No")
        exit()
    for i, j in zip(same, to_swap):
        B[i], B[j] = B[j], B[i]
print("Yes")
print(*B, sep=" ")



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

using namespace std;

const long long MOD = 1e9 + 7;

long long Bin(long long a, long long n) {
	if (n == 0) return 1;
	long long l = Bin(a, n / 2);
	l = (l * l) % MOD;
	if (n & 1) l = (l * a) % MOD;
	return l;
}

long long Rev(long long a) {
	return (Bin(a, MOD - 2));
}

long long Calc(long long k, long long n) {
	long long m1 = 1;
	for (int i = 1; i <= n; i++) {
		m1 *= i;
		m1 %= MOD;
	}
	long long m2 = 1;
	for (int i = 1; i <= k; i++) {
		m2 *= i;
		m2 %= MOD;
	}
	long long m3 = 1;
	for (int i = 1; i <= n - k; i++) {
		m3 *= i;
		m3 %= MOD;
	}
	long long res = m1 * Rev(m2) % MOD * Rev(m3) % MOD;
	return res; 
}

int main() {
	ios::sync_with_stdio(false);
	long long x, y;
	cin>>x>>y;
	if ((x + y) % 3 != 0) {
		cout<<"0\n";
		return 0;
	}
	long long n = (x + y) / 3;
	x -= n;
	y -= n;
	if (x < 0 || y < 0) {
		cout<<"0\n";
		return 0;
	}
	//Answer is c (x) (n): n! / x! / (n - x)!
	cout<<Calc(x, n);
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {

    int n, i, j, max = 0, min = 0, a[10000];
    long long sum = 0;

    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }

    min = max = a[0]; //To be temporarity set maximum value and minimum value.

    for(j = 1; j < n; j++){ //Calc maximum value and mininum value.

        if(min > a[j]){
            min = a[j];
        }

        if(max < a[j]){
            max = a[j];
        }
    }

    printf("%d %d %lld\n", min, max, sum);

    return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define IT set<int>::iterator

using namespace std;
const int N=200000+7;
typedef long long ll;
struct Node{
    ll v;
    int index;
}node[N];
int c[N],n,vis[N];
int cmp(Node a,Node b)
{
    return a.v<b.v;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&node[i].v);
        node[i].index=i;
    }
    ll ans=0;
    sort(node+1,node+1+n,cmp);
    set<int>s;
    s.clear();
    s.insert(0);
    s.insert(n+1);
    for(int i=1;i<=n;i++)
    {
        IT head,tail;
        tail=s.upper_bound(node[i].index);
        head=s.upper_bound(node[i].index);
        head--;
        ans+=node[i].v*(*tail-node[i].index)*(node[i].index -*head);
        s.insert(node[i].index);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define f first
#define s second

vi c[100005];
bool visit[100005];
int ind[100005];
int dp[100005];

void dfs(int x){
	visit[x] = true;
	for(int y : c[x]){
		dp[y] = max(dp[y], dp[x] + 1);
		ind[y]--;
		if(ind[y] == 0){
			dfs(y);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.in", "r", stdin);
        //freopen("output.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a, b;
		cin >> a >> b;
		c[a].pb(b);
		ind[b]++;
	}	
	for(int i = 1; i <= n; i++){
		if(!visit[i] && ind[i] == 0){
			dfs(i);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 9728
#include<bits/stdc++.h>
using namespace std;
    
int main() {    
    int x, y;
    cin >> x >> y;
    int a = 4*x - y;
    if (a % 2 == 0 && a >= 0 && x - a/2 >= 0) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N,A,B;cin >> N >> A >> B;
  int count = 0;
  rep(i,N){
    int x = i+1;
    int num = 0;
    while(x!=0){
      num+=x%10;
      x/=10;
    }
    if(num>=A && num<=B) count += i+1;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <algorithm>
#define llint long long
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;
typedef pair<P, llint> E;

llint S, T;
llint s[2005], t[2005];
llint dp[2005][2005], sum[2005][2005];

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

  cin >> S >> T;
  for(int i = 1; i <= S; i++) cin >> s[i];
  for(int i = 1; i <= T; i++) cin >> t[i];

  for(int i = 1; i <= S; i++){
    for(int j = 1; j <= T; j++){
      if(s[i] == t[j]){
        dp[i][j] = sum[i-1][j-1] + 1, dp[i][j] %= mod;
      }
      sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mod + dp[i][j];
      sum[i][j] %= mod;
    }
  }
  cout << (sum[S][T]+1)%mod << endl;

  return 0;
}


Measured memory_bytes: 62848
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

#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<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;
void yes(bool c) { if (c)print("Yes"); else print("No"); };

int A, B, N;

int f(int x) {
	return A * x / B - A * (x / B);
}

void solve() {

	cin >> A >> B >> N;
	int l = 0, r = N;
	while (r - l > 10) {
		int m1 = (2 * l + r) / 3;
		int m2 = (l + 2 * r) / 3;
		if (f(m1) > f(m2)) {
			r = m2;
		}
		else l = m1;
	}
	ll mx = 0;
	FOR(x, l, r + 1) {
		//pe(x); print(f(x));
		mx = max(mx, f(x));
	}
	print(mx);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
		solve();
}



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


int solve(int a) {
	if(a==2) return true;
	if(a<2 || a%2==0 ) return false;
	
	int i=3;
	while(i<=sqrt(a)) {
		if(a%i==0) return false;
		i=i+2;		
	}
	return true;
}

int main() {
	int n, c=0, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m;
		if(solve(m)) c++;
	}		
	cout << c << endl;
}



Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> l(2*n,0);
	REP(i,2*n)cin >> l[i];
	sort(l.begin(),l.end());
	int ans = 0;
	REP(i,n)ans += l[i * 2];
	cout << ans << 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 rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int H, W;
int c[50][50];

int dfs(int x, int y){
    c[x][y] = 0;
    rep2(i, -1, 1){
        rep2(j, -1, 1){
            int nx = x+i, ny = y+j;
            if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if(c[nx][ny] == 0) continue;
            dfs(nx, ny);
        }
    }
    return 1;
}

int main(){
    while(true){
        cin >> W >> H;
        if(W == 0 && H == 0) break;
        rep(i, H){
            rep(j, W) cin >> c[i][j];
        }
        int ans = 0;
        rep(i, H){
            rep(j, W){
                if(c[i][j]) ans += dfs(i, j);
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3272
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2　//1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) (max(x,y)-min(x,y))
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

signed main(void){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int n;
  string s;
  cin >> n >> s;
  int color[3][4005] = {};
  for(int i = n - 1;i >= 0;i --){
    color[0][i] += color[0][i + 1];
    color[1][i] += color[1][i + 1];
    color[2][i] += color[2][i + 1];
    if(s[i] == 'R'){
      color[0][i] ++;
    } else if(s[i] == 'G'){
      color[1][i] ++;
    } else {
      color[2][i] ++;
    }
    //cout << color[0][i] << " " << color[1][i] << " " << color[2][i] << '\n';
  }
  lol ans = 0;
  rep(i, n){
    for(int j = i + 1;j < n; j ++){
      if(s[i] == 'R'){
	if(s[j] == 'G'){
	  ans += color[2][j + 1];
	  if(s[j + abs(i, j)] == 'B'){
	    ans --;
	  }
	} else if(s[j] == 'B'){
	  ans += color[1][j + 1];
	  if(s[j + abs(i, j)] == 'G'){
	    ans --;
	  }
	}
      }

      else if(s[i] == 'G'){
	if(s[j] == 'R'){
	  ans += color[2][j + 1];
	  if(s[j + abs(i, j)] == 'B'){
	    ans --;
	  }
	} else if(s[j] == 'B'){
	  ans += color[0][j + 1];
	  if(s[j + abs(i, j)] == 'R'){
	    ans --;
	  }
	}
      }

      else {
	if(s[j] == 'G'){
	  ans += color[0][j + 1];
	  if(s[j + abs(i, j)] == 'R'){
	    ans --;
	  }
	} else if(s[j] == 'R'){
	  ans += color[1][j + 1];
	  if(s[j + abs(i, j)] == 'G'){
	    ans --;
	  }
	}
      }
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

const double EPS = 1e-8;

typedef complex<double> Point;

int calc(Point p, vector<Point>& ps){
    int ans = 0;
    for(int i = 0; i < ps.size(); i++){
        if(abs(ps[i] - p) < 1.0 + EPS) {
            ans++;
        }
    }
    return ans;
}
vector<Point> touching_circle(Point a, Point b, double r){
    vector<Point> res;

    double d = abs(b - a);
    if(d > 2 * r) return res;

    Point mid = 0.5 * (a + b);
    Point dir = polar(sqrt(r * r - d * d / 4), arg(b - a) + M_PI / 2);
    res.push_back(mid + dir);
    res.push_back(mid - dir);
    return res;
}
int main(){
    int N;
    while(cin >> N && N){
        vector<Point> ps(N);
        REP(i, N){
            double x, y;
            cin >> x >> y;
            ps[i] = Point(x, y);
        }
        int ans = 1;
        REP(i, N) REP(j, N) if(abs(ps[i] - ps[j]) > EPS) {
            vector<Point> tp = touching_circle(ps[i], ps[j], 1.0);
            for(Point c : tp){
                ans = max(ans, calc(c, ps));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

void Sort(vector<int>& List);
void Output(vector<int>& List);

void Sort(vector<int>& List)
{
	for(int i = 1; i < List.size(); i++){
		int Temp = List[i];
		int j = i - 1;
		while(j >= 0 && List[j] > Temp){
			List[j + 1] = List[j];
			j--;
		}
		List[j + 1] = Temp;
	}
}

void Output(vector<int>& List)
{
	for(int i = 0; i < List.size(); i++){
		if(i > 0)	cout << " ";
		cout << List[i];
	}
	cout << endl;
}

int main()
{
	vector<int> List;
	
	List.clear();
	for(int i = 0; i < 3; i++){
		int Value;
		cin >> Value;
		List.push_back(Value);
	}
	
	Sort(List);
	Output(List);
}

Measured memory_bytes: 1212
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int N;
    cin >> N;
    int a[N];
    int  sum = 0;
    rep(i, N){
        cin >> a[i];
        sum += a[i];
    }
    int res = sum * sum; //各値から平均を引いた値で最小となるもの
    rep(i, N){
        int sub = fabs(N * a[i] - sum);
        res = min(res, sub);
    }
    rep(i, N){
        if(res == abs(N * a[i] - sum)){
            cout << i << endl;
            break;
        }
    }
    return 0;
}

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

using namespace std;

typedef long long int ll;

const ll MAXN = 165 * 80;

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

  ll h, w;
  cin >> h >> w;
  ll a[h + 1][w + 1];
  bool dp[h + 1][w + 1][MAXN];

  for(int i = 0; i <= h; i++){
    for(int j = 0; j <= w; j++){
      for(int k = 0; k < MAXN; k++) dp[i][j][k] = false;
    }
  }

  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      cin >> a[i][j];
    }
  }

  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      ll b; cin >> b;
      a[i][j] = abs(a[i][j] - b);
    }
  }

  dp[0][1][0] = true;
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      for(int k = 0; k < MAXN; k++){
        if(dp[i - 1][j][k]){
          dp[i][j][abs(k - a[i][j])] = true;
          dp[i][j][k + a[i][j]] = true;
        }else if(dp[i][j - 1][k]){
          dp[i][j][abs(k - a[i][j])] = true;
          dp[i][j][k + a[i][j]] = true;
        }
      }
    }
  }

  for(int i = 0; i < 85; i++){
    if(dp[h][w][i]){
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 84864
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    static Scanner sc ;
	public static void main (String[] args) throws java.lang.Exception
	{
	    sc = new Scanner(System.in) ;
	    int n = sc.nextInt() ;
	    HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>() ;
	    for(int i = 0 ; i<n ; i++)
	    {
	        int x = sc.nextInt() ;
	        if(hm.containsKey(x))
	        {
	            hm.put(x,hm.get(x)^1) ;
	        }
	        else
	        {
	            hm.put(x,1) ;    
	        }
	    }
	    int ctr = 0 ;
	    for(int key : hm.keySet())
	    {
	        ctr+=hm.get(key) ;
	    }
	    System.out.println(ctr) ;
	}
}

Measured memory_bytes: 61272
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;

int main()
 {
 	int n,r,m;
 	cin>>n>>r;
 	if(n>=10)
 		m=r;
 	else
 		m=r+100*(10-n);
 	cout<<m<<endl;
 	return 0;
}
 	
 					

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long n;
    long long cnt=0,ans;
    cin >> n;
    vector<long long> a(n);
    map<long long, long long> p;
    for(long long i=0; i<n; i++) {
        cin >> a[i];
        if(!(p.count(a[i]))) p[a[i]]=1;
        else p[a[i]]++;
    }
    for(long long i=1;i<=n; i++) {
        if(p.count(i)) cnt += (p.at(i))*(p.at(i)-1)/2;
    }
    for(long long i=0; i<n; i++) {
        ans=cnt;
        ans -= (p.at(a[i])-1);
        cout << ans << endl;
    }
}

Measured memory_bytes: 11008
<?php
$n = intval(fgets(STDIN));
$MOD = 10**9+7;
for($j = 1;$j <= $n; $j++){
    $J = $j;
    for($i = 2; $i <= $J; $i++){
        if($J % $i == 0){
            @$map[$i]++;
            $J /= $i;
            $i--;
        }
    }
}
$product = 1;
foreach($map as $i => $count){
    $product *= $count + 1;
    $product %= $MOD;
}
echo $product;

Measured memory_bytes: 4728
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-4;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>int LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>int UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}


int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	llint i,n;
	string s;cin>>s;
	n=s.size()+1;
	vector<llint>a(n);
	for(i=0;i<n-1;i++){
		if(s[i]=='<'){maxeq(a[i+1],a[i]+1);}
	}
	REV(a);REV(s);
	llint ans=0;
	for(i=0;i<n-1;i++){
		if(s[i]=='>'){maxeq(a[i+1],a[i]+1);}
	}
	for(i=0;i<n;i++){ans+=a[i];}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 4764
// template version 1.12
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

// varibable settings
#define infile "../test/sample-1.in"
#define int long long //{{{
const int INF=1e18;
const int MOD=1e9+7; //}}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

// 隣接リストで使う辺を表す型
struct Edge {
  int to, cost;  // 辺の接続先頂点, 辺の重み
  Edge(int to, int cost) : to(to), cost(cost) {}  // コンストラクタ
};

typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;  // グラフの辺を格納した構造体
                // graph[v][i]は頂点vから出るi番目の辺Edge

vector<int> dist; // 最短距離

int solve(){
    int h,w,ans;cin>>h>>w;
    //string s,ans;
    string s[100];
    rep(i,h){
        cin>>s[i];
    }
    int r[100];
    int c[100];
    rep(i,h){r[i]=w;}
    rep(i,w){c[i]=h;}
    
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='.'){
                r[i]-=1;
                c[j]-=1;
            }
                
        }
    }
    rep(i,h){
        if(r[i]==0)continue;
        rep(j,w){
            
            if(c[j]>0)cout<<s[i][j];
        }
        
        cout<<endl;
    }
    
    //cout << ans << endl;
    
    return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "{";
	rep(i, v.size()) {
		if (i) os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}
template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >>p.second ;
	return is;
}
template <class T>istream& operator>>(istream& is,  vector<T>& v) {
	rep(i, v.size()) {
		is >> v[i];
	}
	return is;
}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n,k;
	ll ans=-INFLL;
	cin >>n>>k;
	vector<vector<pair<int, ll>>> tri(n, vector<pair<int,ll>>(33,mp(0,0LL)));
	VV up(n, V(33, 0LL));
	rep(i, n) { cin >> tri[i][0].F ;
		tri[i][0].F--;
		
	}
	rep(i, n) { cin >> tri[i][0].S;
		up[i][0] = tri[i][0].S;
	}
	rep(j,31){
		rep(i, n) { 
			tri[i][j + 1].F = tri[tri[i][j].F][j].F;
			tri[i][j + 1].S = tri[i][j].S+tri[tri[i][j].F][j].S;
			up[i][j + 1] =
			    max(up[i][j], tri[i][j].S + up[tri[i][j].F][j]);
		 }
	
	}
	/*
	rep(i,30){
		rep(j, n) { clog << tri[j][i] << " "; }
		clog << endl;
	}
	clog << endl;
	rep(i,30){
		rep(j, n) { clog << up[j][i] << " "; }
		clog << endl;
	}
	*/
	int at = 0;
	ll cnt = 0;
	for (int st = 0; st < n;st++){
		at = st;
		cnt = 0LL;
		for (int i = 0; k >= (1LL << i); i++) {
			if (k & (1LL << i)) {
				chmax(ans, cnt + up[at][i]);
				cnt += tri[at][i].S;
				at = tri[at][i].F;
				chmax(ans, cnt);
			//	clog << at <<" "<< cnt << endl;
			}
		}
	//	clog << ans << endl;
	    }cout << ans << endl;
}

Measured memory_bytes: 7824
import Data.List

main = getLine >> getLine >>= print.solve.map read.words
solve as = min (f bs) (f cs) where
  bs = snd $ unzip $ scanl f (10^9, -1) as where
    f (mi,_) a = let m = min mi a in (m, a-m)
  cs = snd $ unzip $ scanr f (0, -1) as where
    f a (ma,_) = let m = max a ma in (m, m-a)
  f xs = length $ filter (==ma) xs where ma = maximum xs

Measured memory_bytes: 54652
#include <stdio.h>

int main(){
	double a,b,c,d,e,f, x,y,dd;
	while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)>0){
		dd = (a*e-b*d);
		x=(c*(a*e-b*d)/a-b*f+c*d*b/a)/dd;
		y=(a*f-c*d)/dd;
		if(x==0)x=0;
		printf("%.3f %.3f\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int m=-1,n=-1,i;
	for(i=0;i<s.size();i++)
	{
		if(s[i]=='C')
		{
			m=i;
		}
		if(s[i]=='F')
		{
			n=i;
		}
	}
	if(m!=-1&&n!=-1&&m<n)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl; 
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<ll>a(n);
    vector<ll>b(n);
    rep(i, 0, n)cin >> a[i];
    rep(i, 0, n)cin >> b[i];
    ll sum1=0, sum2=0;
    rep(i, 0, n){
        if(a[i]-b[i]>0)sum1 -= (a[i]-b[i]);
        else sum1 += (b[i]-a[i])/2;
    }
    if(sum1 >=0)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 384
#include"bits/stdc++.h"
using namespace std;
struct c {
	int d;
	char str[10];
};
c e;
queue <c> w;
int main() {
	int n, q,sum=0,sum2=0;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> e.str;
		cin >> e.d;
	    w.push(e);
	}
	while (!w.empty()) {
		e = w.front();
		if (e.d - q > 0) {
			e.d = e.d - q;
			sum += q;
			w.pop();
			w.push(e);
		}
		else {
			sum += e.d;
			cout << e.str << " " << sum << endl;
			w.pop();
		}
	}
	return 0;
}

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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N, S;
int X[110000], P[110000];
signed main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++)cin >> X[i] >> P[i];
    int l = 0, r = N - 1;
    int ans = 0, dir = -1;
    for (int i = 0; i < N; i++) {
        if (S < X[l]) {
            cout << ans + X[r] - S << endl;
            return 0;
        }
        if (S > X[r]) {
            cout << ans + S - X[l] << endl;
            return 0;
        }
        if (P[l] >= P[r]) {
            if (dir != 0)ans += X[r] - X[l];
            P[l] += P[r];
            r--;
            dir = 0;
        } else {
            if (dir != 1)ans += X[r] - X[l];
            P[r] += P[l];
            l++;
            dir = 1;
        }

    }
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;

int f(int a, int k) {
	if (a < k) return 0;
	if (a % k == 0) return (a/k);
	int r = a%k;
	int q = a/k;
	if (r < q+1) {
		return f((k-1)*q + ((r-1)), k);
	} else {
		return f(k*q + (r%(q+1)), k);
	}
}

int main() {
	make(n);
	int ans  = 0;
	FOR(i,0,n) {
		make2(a, b);
		ans ^= f(a, b);
	}
	if (ans == 0) printf("Aoki\n");
	else printf("Takahashi\n");
}


Measured memory_bytes: 256
N = int(input())
A = [int(n) for n in input().split()]
print(" ".join(map(str, A)))
for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(" ".join(map(str, A)))



Measured memory_bytes: 5604
import java.util.*;
import java.util.regex.*;

class Main{
	public static void main(String[]z){
		Scanner cin=new Scanner(System.in);
		String s=cin.next();
		String t=cin.next().replaceAll("_",".");
		Matcher m=Pattern.compile(t).matcher(s);
		System.out.println(m.find()?"Yes":"No");
	}
}


Measured memory_bytes: 20440
"""
author : halo2halo
date : 12, Jan, 2020
"""

import sys

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

S = set(readline().decode('utf8').rstrip())
print('Yes' if len(S) == 2 else 'No')


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#define _USE_MATH_DEFINENS
#include <cmath>
using namespace std;

#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);

    int n;
    cin >> n;
    cout << n * (n + 1) / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define dump(x) cout << #x << " = " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int siz = S.size();
  int sum = 0;
  for(int i = 0; i < siz; i++) {
    if(S[i] == 'o') { sum++; }
  }
  sum += 15 - siz;
  if(sum >= 8) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

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

using namespace std;

int binary_search(int a[],int k,int n) {
	int l = 0, r = n-1, cnt=0;

	while (r - l >= 0) {
		int m = (l + r) / 2;
		cnt++;
		if (a[m] == k) return cnt;
		else if (a[m] > k) {
			r = m-1;
		}
		else if (a[m] < k) {
			l = m + 1;
		}
	}

	return cnt;
}

int main() {
	
	int n;

	while (cin>>n) {

		if (n == 0)
			return 0;

		int a[100010], k, ans;

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

		cin >> k;

		ans=binary_search(a, k, n);

		cout << ans<<endl;
	}
}

Measured memory_bytes: 2996
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int t = scanner.nextInt();
        final int a = scanner.nextInt();

        final double[] d = new double[n];
        for (int i = 0; i < n; i++) {
            final int h = scanner.nextInt();
            d[i] = Math.abs(a - (t - 0.006 * h));
        }

        int minIndex = 0;
        double minDiff = d[0];
        for (int i = 1; i < n; i++) {
            if (minDiff > d[i]) {
                minDiff = d[i];
                minIndex = i;
            }
        }

        System.out.println(minIndex + 1);
    }

}


Measured memory_bytes: 22868
#include<iostream>
#include<math.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int rem = n%10;
  if(rem==2 || rem==4 || rem==5 || rem==7 || rem==9)
    cout<<"hon"<<endl;
  else if(rem ==0 || rem==1 || rem==6 || rem==8)
    cout<<"pon"<<endl;
  else
    cout<<"bon"<<endl;


  
  
  
  
  
 return 0; 
}

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(100003);
	rep(i, n) cin >> a[i];
	rep(i, n) {
		b[a[i]]++;
		if(a[i]>0) b[a[i]-1]++;
		b[a[i]+1]++;
	}
	int ans = 0;
	rep(i, b.size()) ans = max(ans, b[i]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024