akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()

using namespace std;


signed main()
{
	int N;
	char S[1000];
	cin >> N;
	cin >> S;
	if (N % 2 != 0)
	{
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < N / 2; i++)
	{
		if (S[i] != S[i + N / 2])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, M);
  vl a(N), b(N), c(M), d(M);
  rep(i, 0, N) {
    in(a[i], b[i]);
  }
  rep(i, 0, M) {
    in(c[i], d[i]);
  }
  rep(i, 0, N) {
    ll mn = LINF;
    ll best;
    rep(j, 0, M) {
      ll dist = abs(a[i] - c[j]) + abs(b[i] - d[j]);
      if (dist < mn) {
        best = j + 1;
        mn = dist;
      }
    }
    print(best);
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vl v(n);
	rep(i,n)cin>>v[i];
	ll ans=LINF;
	rep(i,101){
		ll sum=0;
		rep(j,n)sum+=(v[j]-i)*(v[j]-i);
		chmin(ans,sum);
	}
	puta(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <vector>
#include <algorithm> // sort
#include <map>
using namespace std;

using ll = long long int;
using ppi=pair<ll,ll>;
using pql =priority_queue<ll, vector<ll>, greater<ll>>;
using pq=priority_queue<ll>;

int main(){
    int k,n;
    cin>>k>>n;
    int a,b,f,m;
    m=0;
    cin>>a;
    f=a;
    for(int i=0;i<n-1;i++){
        cin>>b;
        m=max(m,b-a);
        a=b;
    }
    m=max(m,f+k-a);
    cout<<k-m<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;
const long long mod=1000000007;
const long long inf=1ll<<61;

signed main(){
    int n;cin>>n;
    double bo;
    rep(i,n){
        int a;cin>>a;
        bo+=1.0/(double)a;
    }
    cout<<fixed<<setprecision(13)<<1.0/bo<<endl;
}

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

using ll = long long int;
using P = std::pair<int, int>;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rag(con) std::begin(con), std::end(con)

int main()
{
    std::string s, t;
    std::cin >> s >> t;

    int ans = t.size();

    rep(i, s.size() - t.size() + 1)
    {
        int res = 0;
        rep(j, t.size())
        {
            if (t[j] == s[j + i])
                ++res;
        }
        ans = std::min(ans, (int)t.size() - res);
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 3616
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[100005],cnt[200005];
template < typename T > T MAX(T a,T b){
	return a>b?a:b;
}
int main(){
	scanf("%d",&n);
	int xb,x2;
	for(xb=0;xb<n;xb++) scanf("%d",a+xb);
	for(xb=0;xb<n;xb++){
		cnt[a[xb]]++;
		cnt[a[xb]+1]++;
		cnt[a[xb]+2]++;
	}
	int val=0;
	for(xb=0;xb<200005;xb++) val=MAX(val,cnt[xb]);
	printf("%d\n",val);
	return 0;
}

Measured memory_bytes: 896
A, B = map(int, input().split())
if A%0.08 == 0:
    a_min = int(A/0.08)
else:
    a_min = int(A//0.08) + 1
a_max = (A+1)//0.08

result = -1
for i in range(int(a_min), int(a_max)+1):
    if (i*0.1//1 == B)*(i*0.08//1 == A):
        result = i
        break
print(result)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 1001001001;

int main(){
  int r,c,k;
  cin >> r >> c >> k;

  static ll g[4000][4000] = {0};
  rep(i,k){
    int y,x;
    ll v;
    cin >> y >> x >> v;
    y--; x--;//start from (0,0)
    g[y][x] = v;
  }

  static ll dp[4000][4000][4];
  if(g[0][0] != 0) dp[0][0][1] = g[0][0];
  dp[0][0][0] = 0;

  rep(i,r){
    rep(j,c){

      //move in a row
      if(g[i][j+1] != 0){
        // not get
        dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0]);   
        dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][1]);
        dp[i][j+1][2] = max(dp[i][j+1][2], dp[i][j][2]);
        dp[i][j+1][3] = max(dp[i][j+1][3], dp[i][j][3]);
        // get
        dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][0]+g[i][j+1]);
        dp[i][j+1][2] = max(dp[i][j+1][2], dp[i][j][1]+g[i][j+1]);
        dp[i][j+1][3] = max(dp[i][j+1][3], dp[i][j][2]+g[i][j+1]);
      }else{
        dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0]);
        dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][1]);
        dp[i][j+1][2] = max(dp[i][j+1][2], dp[i][j][2]);
        dp[i][j+1][3] = max(dp[i][j+1][3], dp[i][j][3]);
      }

      //move int a column
      if(g[i+1][j] != 0){
        //not get
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][0]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][2]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][3]);
        //get
        dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0]+g[i+1][j]);
        dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][1]+g[i+1][j]);
        dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][2]+g[i+1][j]); 
        dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][3]+g[i+1][j]);
      }else{
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][0]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][2]);
        dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][3]);
      }
    }
  }

  
  ll ans = 0;
  rep(i,4) ans = max(ans, dp[r-1][c-1][i]);
  cout << ans << endl;
  

}


Measured memory_bytes: 377612
#include<iostream>

using namespace std;

int main(){
    int A, B, a, b, c, buf;
    cin >> A >> B;
    a = A + B;
    b = A - B;
    c = A * B;
    if(a > b){
        buf = a;
        a = b;
        b = buf;
    }
    if(b > c){
        buf = b;
        b = c;
        c = buf;
    }
    if(a > b){
        buf = a;
        a = b;
        b = buf;
    }
    cout << c << endl;

    return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.buffer.readline
    from heapq import heappop, heappush
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    Q, K = (int(i) for i in input().split())
    dist = dijkstra(edge, K-1)
    for q in range(Q):
        x, y = (int(i)-1 for i in input().split())
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()


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

//~ #pragma GCC optimize("O3")

using namespace std;

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

typedef long long ll;

void solve(){
	int k, n;
	cin >> k >> n;
	vector<int> dis(n);
	for(int i = 0; i < n; ++i) cin >> dis[i];
	int bigger = 0;
	int sum = 0;
	for(int i = 0; i < n; ++i) {
		int value;
		if(i < n - 1) {
			value = dis[i+1] - dis[i];
			sum += value;
		} else {
			value = k - dis[i] + dis[0];
			sum += value;
		}
		
		if(value > bigger) bigger = value;
	}
	cout << sum-bigger;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();
    
    return 0;
}


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

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

int main(){
    int A,B;
    int max;
    cin >> A >> B;

    max = A + B;
    if( max < A - B){
        max = A - B;
    }
    if( max < A * B){
        max = A * B;
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    String S =sc.next();
    String T =sc.next();
    int s =S.length();
    String t =T.substring(0,s);
    if(t.equals(S)){System.out.println("Yes");}
    else{System.out.println("No");}
  }
}

Measured memory_bytes: 35704
import java.util.*;
import java.awt.geom.*;
import java.io.*;

public class Main{
	int m, year;
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		int dataset = sc.nextInt();
		while(dataset-- > 0){
			m = sc.nextInt();
			year = sc.nextInt();
			int n = sc.nextInt();
			int max = 0;
			while(n-- > 0){
				int digit = sc.nextInt();
				double r = sc.nextDouble();
				int t = sc.nextInt();
				int res = solve(digit, r, t);
				max = Math.max(max, res);
			}
			System.out.println(max);
		}
	}

	private int solve(int digit, double r, int t) {
		int a = m;
		if(digit == 1){
			for(int i = 0; i < year; i++){
				int b = (int) (a * r);
				a = a + b - t;
			}
		}
		else{
			int b = 0;
			for(int i = 0; i < year; i++){
				b += (int) (a * r);
				a -= t;
			}
			a = a + b;
		}
		return a;
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}
}

Measured memory_bytes: 42808
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e9;

int main(){
  int N,M;cin>>N>>M;
  int left=0,right=INF,l,r;
  while(M--){
    cin>>l>>r;
    left=max(left,l);
    right=min(right,r);
  }
  print(max(right-left+1,0))
}


Measured memory_bytes: 256
#include<bits/stdc++.h>    
using namespace std;
#define ll long long 
#define pi pair<ll,ll>
#define pd pair<ld,ld>
#define pb push_back
#define inf 1e15
#define mod 1000000007
#define en '\n'
#define ld long double
#define ff first
#define ss second
#define ull unsigned long long 
#define lb lower_bound
#define ub upper_bound
#define fr(a,b,c) for(ll a = b ; a <= c ; ++a )
#define frn(a,b,c) for(ll a = b ; a >= c ; a -- )
#define fra(a,b) for(auto a: b)
#define ms(a) memset(a,0,sizeof a);
#define alla(a) a,a+n
#define allv(a) a.begin(),a.end()
#define size(a) (ll)a.size()
#define getMat(x,n,m,val) vector<vector<ll>>x(n,vector<ll>(m,val))
const ll MAXN = 1e5+5;
#define pii 3.14159265358979323846 
ll pw(ll b, ll r, ll md){
	ll ans = 1;
	while(r){
		if(r&1)ans = (ans*b)%md;
		b = (b*b)%md;
		r>>=1;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll k;cin>>k;
	bool dp[k+1];ms(dp);
	ll ans = 0 ;
	ll sub = 0 ;  
	bool flag = true;
	while(true){
		sub = sub*10+7;
		sub%=k;
		ans++;
		if(sub==0)break;
		if(dp[sub]){
			flag = false;
			break;
		}
		dp[sub]=true;
	}
	if(flag)cout<<ans<<en;
	else cout<<-1<<en;
	return 0 ;

}

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


int W,H,N;


int main(void)
{

	while(cin >> W >> H, W | H){
	
	cin >> N;

	int a,b;
	int load[120][120] = {};
	for(int i = 0; i < N; i++){
		cin >> a >> b;
		load[b][a] = -1;
	}
	load[1][1] = 1;
	
	for(int i = 1; i <= 100; i++){
		for(int j = 1; j <= 100; j++){
			if(load[i][j] >= 0 && load[i][j+1] >= 0)
				load[i][j+1] += load[i][j];
			if(load[i][j] >= 0 && load[i+1][j] >= 0)
				load[i+1][j] += load[i][j];
		}
	}
	cout << load[H][W] << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	ll a,b; cin >> a >> b;
	vector<ll> h(n);
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	ll left=0,right=1e9+5;
	while(right-left>1){
		ll mid=(left+right)/2;
		ll sum=0;
		for(int i=0;i<n;i++){
			if(h[i]-mid*b<=0)continue;
			else{
				sum+=(h[i]-mid*b+(a-b)-1)/(a-b);
			}
		}
		if(sum<=mid){
			right=mid;
		}else{
			left=mid;
		}
	}
	cout << right << endl;
}

Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    print(math.ceil(N / 2))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100"""
        output = """50"""
        self.assertIO(input, output)


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

using namespace std;

int main()
{
    int n,i,j,m;
    string s,s1,s2;
    cin>>s;
    n=s.length();
    m=(n+1)/2-1;
    for(i=0;i<m;i++)
    {
        if(s[i]!=s[n-1-i])
        {
            cout<<"No";
            return 0;
        }
    }
    for(i=0;i<m;i++)
    {
        if(s[i]!=s[m-1-i])
        {
            cout<<"No";
            return 0;
        }
    }
    for(i=m+1;i<n;i++)
    {
        if(s[i]!=s[n-1-(i-m-1)])
        {
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
    
}


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

void c_p_c()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int main()
{
    c_p_c();
    int n, m;
    cin >> n;
    int y = 1000 - n % 1000;
    if (n % 1000 == 0) cout << 0 << endl;
    else cout << y << endl;
    return 0;
}

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

int main(){
  int h,w,n;cin>>h>>w>>n;
  vector<int> a(h*w,0);
  vector<vector<int>> m(h,vector<int>(w,0));

  int c=0;
  REP(i,n){
    int t;cin>>t;
    REP(j,t){
      a.at(c)=i+1;
      c++;
    }
  }

  c=0;
  REP(i,h){
    if(!(i%2)) for(int j=0;j<w;j++){
      m.at(i).at(j)=a.at(c);
      c++;
    }else for(int j=w-1;j>=0;j--){
      m.at(i).at(j)=a.at(c);
      c++;      
    }
  }

  REP(i,h){
    REP(j,w) cout<<m.at(i).at(j)<<" ";
    cout<<endl;
  }
  
}


Measured memory_bytes: 384
#include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 typedef long long ll;
 int main()
 {
	 vector<int> v;
	 int a;
	 cin >> a;
	 for (int i = 0; i < a; i++)
	 {
		 int s;
		 cin >> s;
		 v.push_back(s);
	 }
	 sort(v.begin(), v.end());
	 cout << v[a / 2] - v[a / 2 - 1] << endl;
	 return 0;
 }


Measured memory_bytes: 892
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using lint = long long;
using namespace std;

const int MOD = 1000000007;
const lint INF = 1LL << 60;

const double PI = acos(-1);
const double Rad2Deg = 180.0 / PI;
const double Deg2Rad = PI / 180.0;

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

    if (X % 100 == 0) {
        cout << "1" << endl;
        return 0;
    }

    int XM = X % 100;
    int MAX = X / 100;
    int ans = 0;

    for (int a = 0; a <= 20; a++) {
        for (int b = 0; b <= 20; b++) {
            for (int c = 0; c <= 20; c++) {
                for (int d = 0; d <= 20; d++) {
                    for (int e = 0; e <= 20; e++) {
                        int sum = a + 2 * b + 3 * c + 4 * d + 5 * e;
                        int sc = a + b + c + d + e;
                        if (sum == XM && sc <= MAX) {
                            ans = 1;
                        }
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d",&a)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%ld\n",a)
#define pll(a) printf("%lld\n",a) 
#define sc(a) scanf("%c",&a)a
#define pc(a) printf("%c",a)
#define ll long long
#define ld long double
#define mod 1000000007

#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF INT_MAX
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define VI vector<int>
#define VL vector<ll>
#define PI pair<int,int>
#define PL pair<ll,ll>
long double PIE=acos(-1);
//////////////////////////////////////////////////////////////
const ll N=1e5+5;
ll Ans=1;
bool done[1000009];
vector < ll > primes;

void FindPrime(ll N)
{
    done[1] = 1;
    for(int i=2;i<=N;i++)
	{
        if(done[i]) continue;
        for(int j=i*2;j<=N;j+=i)
		{
            done[j] = 1;
        }
        primes.push_back(i);
    }
}

ll solve(ll Num)
{
    for(int i=0;i<primes.size();i++)
	{
    	int p=primes[i];
        if(p*p*p > Num) break;
        ll Count = 1;
        while(Num%p == 0)
		{
            Num /= p,Count++;
        }
        Ans *= Count;
    }
    ll sq = (ll)sqrt(Num);
    if(!done[Num]) 
	Ans *= 2;
    else if(sq*sq == Num && !done[sq]) 
	Ans *= 3;
    else if(Num != 1) 
	Ans *= 4;
    return Ans;
}


ll fact[N], invfact[N];



ll pow(ll a, ll b, ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

ll modinv(ll k)
{
	return pow(k, mod-2, mod);
}


ll nCr(ll x, ll y)
{
	if(y>x)
		return 0;
	ll num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}

void initinv()
{
	fact[0]=1;
	fr(i,1,N)
	{
		fact[i]=(i*fact[i-1])%mod;
	}
	invfact[N]=modinv(fact[N]);
	for(int i=N-1;i>=1;i--)
	{
		invfact[i]=((i+1)*invfact[i+1])%mod;
	}
}
///////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
ll dp[3005][3005];
int main()
{
	int n;
	cin>>n;
	ll a[n+1];
	fr(i,1,n)
	cin>>a[i];
	for(int i=n;i>=1;i--)
	{
		for(int j=i;j<=n;j++)
		{
			dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);
		}
	}
	cout<<dp[1][n];
	return 0;
}





Measured memory_bytes: 49736
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int N;
int t[114514];

int64_t count[114514];
int64_t cost[114514];

int soinsuCount;
int soinsu[32][2];

int yakusuCount;
int yakusu[114514];

void getYakusu(int idx, int current) {
	if (idx >= soinsuCount) {
		yakusu[yakusuCount++] = current;
	} else {
		int mofu = current;
		int i;
		for (i = 0; i <= soinsu[idx][1]; i++) {
			getYakusu(idx + 1, mofu);
			mofu *= soinsu[idx][0];
		}
	}
}

int main(void) {
	int i;
	int makkusu = 0;
	int64_t answer = 0;
	int kugyu;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &t[i]) != 1) return 1;
		count[t[i]]++;
		if (t[i] > makkusu) makkusu = t[i];
	}
	for (i = 1; i <= makkusu; i++) {
		count[i] += count[i - 1];
		cost[i] = cost[i - 1] + count[i - 1];
	}
	kugyu = makkusu;
	soinsuCount = 0;
	for (i = 2; i * i <= kugyu; i++) {
		if (kugyu % i == 0) {
			int c = 0;
			while (kugyu % i == 0) {
				kugyu /= i;
				c++;
			}
			soinsu[soinsuCount][0] = i;
			soinsu[soinsuCount][1] = c;
			soinsuCount++;
		}
	}
	if (kugyu > 1) {
		soinsu[soinsuCount][0] = kugyu;
		soinsu[soinsuCount][1] = 1;
		soinsuCount++;
	}
	yakusuCount = 0;
	getYakusu(0, 1);
	qsort(yakusu, yakusuCount, sizeof(*yakusu), cmp);
	answer = cost[yakusu[0]];
	for (i = 1; i < yakusuCount; i++) {
		answer += cost[yakusu[i]] - (count[yakusu[i - 1]] * (yakusu[i] - yakusu[i - 1])) - cost[yakusu[i - 1]];
	}
	printf("%" PRId64 "\n", answer);
	return 0;
}

/*
sukunakutomo itiban nagai yatu yori mizikaku dekinai
*/



Measured memory_bytes: 2280
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define double long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define mod 1000000007
#define ceil(a,b) (a+b-1)/b
#define endl "\n"

#define oa(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define o1(a) cout<<" "<<#a<<" : "<<a<<"\n"
#define o2(a,b) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define o3(a,b,c) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define o4(a,b,c,d) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"

 const int N=100005;
 const int inf=1e18;
 const double eps=1e-9;
int pow1(int a,int b){
    int res=1;
    while(b>0){
        if(b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	bool f=0;
    int k,a,b;
    cin>>k>>a>>b;
    for(int x=a;x<=b;x++){
        if(x%k==0){
            f=1;
            break;
        }
    }
    if(f){
        cout<<"OK";
    }else{
        cout<<"NG";
    }








	
return 0;
}


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

#ifdef DEBUG
#define LOG(var, sep) (cerr << #var << " = " << (var) << (sep))

#define LOGM(msg) (cerr << (msg))

#define LOGV(vec, sep) {                                        \
    cerr << #vec << " =";                                       \
    for (const auto& v : (vec)) cerr << " " << v;               \
    cerr << (sep); }

#define LOGA(arr, N, sep) {                                     \
        cerr << #arr << " =";                                   \
        for (int i = 0; i < N; ++i) cerr << " " << (arr)[i];    \
        cerr << (sep); }

#define LOGA2(arr, N, M, sep) {                                 \
        cerr << #arr << " =\n";                                 \
        for (int i = 0; i < N; ++i) {                           \
            for (int j = 0; j < M; ++j)                         \
                cerr << (arr)[i][j] << " ";                     \
            cerr << endl;                                       \
        } cerr << (sep); }
#else
#define LOG(var, sep)
#define LOGM(msg)
#define LOGV(vec, sep)
#define LOGA(arr, N, sep)
#define LOGA2(arr, N, M, sep)
#endif

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 1000010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

int hist[MAX];
bitset<MAX> sieve;

bool pairwise()
{
    sieve.set();

    ll count = 0;

    for (ll i = 2; i < MAX; i += 2)
        count += hist[i];

    if (count > 1)
        return false;

    for (ll i = 3; i < MAX; i += 2)
    {
        if (not sieve[i])
            continue;

        count = 0;

        for (ll j = i; j < MAX; j += i)
        {
            sieve[j] = false;
            count += hist[j];
        }

        if (count > 1)
            return false;
    }

    return true;
}

string solve(int N, const vector<ll>& xs)
{
    for (auto x : xs)
        ++hist[x];

    if (pairwise())
        return "pairwise coprime";

    ll d = gcd(xs[0], xs[1]);

    for (int i = 2; i < N; ++i)
        d = gcd(xs[i], d);

    return d == 1 ? "setwise coprime" : "not coprime";
}

int main()
{
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<ll> xs(N);

    for (int i = 0; i < N; ++i)
        cin >> xs[i];

    auto ans = solve(N, xs);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 15144
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct eg{int v,nx,w;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}
int dis[N],c[3],eg,sz,fl,n,m;ll ans;
void dfs(int u,int w){
	dis[u]=w,++c[w],++sz;
	go(u){
		++eg;
		if(dis[v]==-1)dfs(v,(dis[u]+e[i].w)%3);
		else if(dis[v]!=(dis[u]+e[i].w)%3)fl=0;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(R int i=1,u,v;i<=m;++i)scanf("%d%d",&u,&v),add(u,v,1),add(v,u,2);
	memset(dis,-1,(n+1)<<2);
	fp(i,1,n)if(dis[i]==-1){
		eg=sz=c[0]=c[1]=c[2]=0,fl=1;
		dfs(i,0);eg>>=1;
		if(fl)ans+=(!c[0]||!c[1]||!c[2]?eg:1ll*c[0]*c[1]+1ll*c[1]*c[2]+1ll*c[2]*c[0]);
		else ans+=1ll*sz*sz;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 6528
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
vector<P>edge[3005];
ll nearest[3005];
ll d[3005];
int n,m,k;
void dijkstra(int k)
{
	fill(d,d+3005,1e12);
	d[k]=0LL;
	priority_queue<P,vector<P>,greater<P> >que;
	que.push(mp(d[k],k));
	while(!que.empty())
	{
		P p=que.top(); que.pop();
		if(d[p.second]!=p.first) continue;
		
		for(int i=0;i<edge[p.second].size();i++)
		{
			if(d[edge[p.second][i].first]>d[p.second]+edge[p.second][i].second)
			{
				d[edge[p.second][i].first]=d[p.second]+edge[p.second][i].second;
				que.push(mp(d[edge[p.second][i].first],edge[p.second][i].first));
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		nearest[i]=min(nearest[i],d[i]);
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;i++)
	{
		ll a,b,c; scanf("%lld %lld %lld",&a,&b,&c);
		edge[a].pb(mp(b,2*c));
		edge[b].pb(mp(a,2*c));
	}
	fill(nearest,nearest+3005,1e12);
	
	for(int i=0;i<k;i++)
	{
		int point;
		scanf("%d",&point);
		dijkstra(point);
	}
	ll ret=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<edge[i].size();j++)
		{
			ret=max(ret,(nearest[i]+nearest[edge[i][j].first]+edge[i][j].second)/2);
		}
	}
	printf("%lld\n",(ret+1)/2);
}

Measured memory_bytes: 7004
n=int(input())
a=list(map(int,input().split()))
a.sort()
c=0
for i in range(n-1,0,-1):
  l = 0
  r = i - 1
  while(l < r):
    if(a[l] + a[r] > a[i]):
      c += r - l
      r -= 1
    else:
      l += 1
print(c)



Measured memory_bytes: 41452
import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args){
        FastScanner fsc=new FastScanner();
        int a=fsc.nextInt(), b=fsc.nextInt();
        fsc.close();
        int ans=0;
        for(int i=a;i<=b;i++){
            char[] c=String.valueOf(i).toCharArray();
            boolean ok=true;
            for(int j=0;j<c.length;j++){
                if(c[j]!=c[c.length-j-1]){
                    ok=false;
                }
            }
            if(ok) ans++;
        }
        System.out.println(ans);
    }
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte(){
            if(ptr<buflen) return true;
            else{
                ptr = 0;
                try{
                    buflen = in.read(buffer);
                }
                catch(IOException e){
                    e.printStackTrace();
                }
                if(buflen<=0) return false;
            }
        return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) throw new NumberFormatException();
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }
                else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
                else throw new NumberFormatException();
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
        public void close(){
            try{in.close();}
            catch(IOException e){e.printStackTrace();}
        }
    }
}


Measured memory_bytes: 29140
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let n: usize = read_as_vec()[0];
    let mut v: Vec<Vec<u64>> = vec![vec![0;n];26];

    for i in 0..n{
        let s = read_as_string();
        for c in s.chars(){
            v[c as usize - 'a' as usize][i] += 1;
        }
    }

    for i in 0..26{
        if v[i].iter().all(|x| *x > 0){
            for _ in 0..*v[i].iter().min().unwrap(){
                print!("{}", (i as u8 + 'a' as u8) as char);
            }
        }
    }

    println!("");
}


Measured memory_bytes: 4352
a, b, c = map(int, input().split())

if a <= b:
    start_num = a
else:
    start_num = b
cnt = 0
for num in range(start_num, 0, -1):
    if (a % num == 0) and (b % num == 0):
        cnt += 1
        if cnt == c:
            print(num)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
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;
}
#define DEBUG
#ifdef DEBUG
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 << '{';
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) {
            os << ',';
        }
        os << v[i];
    }
    os << '}';
    return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
    cerr << " " << x;
    debugg(args...);
}
#define debug(...)                                                             \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __Setup;

using ll = long long;
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

const int max_log = 60;

int main() {
    ll N, X, M;
    cin >> N >> X >> M;
    vector dub(max_log, vector<ll>(M));
    vector sum(max_log, vector<ll>(M));
    for(ll i = 0; i < M; i++) {
        dub[0][i] = i * i % M;
        sum[0][i] = i;
    }
    for(int k = 0; k < max_log - 1; k++) {
        for(int i = 0; i < M; i++) {
            dub[k + 1][i] = dub[k][dub[k][i]];
        }
        for(int i = 0; i < M; i++) {
            sum[k + 1][i] = sum[k][i] + sum[k][dub[k][i]];
        }
    }
    ll ans = 0;
    for(int i = 0; i < max_log; i++) {
        if(N & (1LL << i)) {
            ans += sum[i][X];
            X = dub[i][X];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 97892
S = input()
l = len(S)
T = ''.join(list(reversed(S)))

a = S[:(l-1)//2]
a1 = ''.join(list(reversed(a)))

b = S[(l+3)//2-1:l]
b1 = ''.join(list(reversed(b)))

if S == T:
    if a == a1 and b == b1:
        print('Yes')
    if a != a1 or b != b1:
        print('No')
if S != T:
    print('No')

Measured memory_bytes: 9008
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "cmath"
#include "random"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;


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

	cin >> N;
	long long int ans = 1;
	vector<long long int>a(N);
	vector<long long int>b(N);
	vector<long long int>v(2 * N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		v[i] = a[i] * 1000000;
	}
	for (int i = 0; i < N; i++) {
		cin >> b[i];
		v[N + i] = b[i] * 1000000 + 1;
	}
	sort(v.begin(), v.end());
	long long int box = 0;
	long long int bag = 0;
	for (auto i : v) {
		if (i % 2) {
			if (box) {
				ans *= box;
				box--;
				ans %= MOD;
			}
			else {
				bag++;
			}
		}
		else {
			if (bag) {
				ans *= bag;
				bag--;
				ans %= MOD;
			}
			else {
				box++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
long long dp[3002][3002][4];
int main(){
    int R, C, K;
    cin >> R >> C >> K;
    long long grid[R + 3][C + 3];
    for(int i = 0; i <= R; i++){
        for(int j = 0; j <= C; j++){
            grid[i][j] = 0;
            dp[i][j][0] = 0;
            dp[i][j][1] = -1e18;
            dp[i][j][2] = -1e18;
            dp[i][j][3] = -1e18;
        }
    }
    for(int i = 1; i <= K; i++){
        int r, c;
        long long v;
        cin >> r >> c >> v;
        grid[r][c] = v;
    }
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j][0]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][1]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][2]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][3]);
            dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0]);
            if(grid[i][j] > 0){
                dp[i][j][1] = max(dp[i][j][1], dp[i][j][0] + grid[i][j]);
            }
            if(grid[i][j] > 0){
                for(int k = 3; k >= 1; k--){
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + grid[i][j]);
                }
            }
            for(int k = 0; k <= 3; k++){
                dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
            }
        }
    }
    long long ans = max(dp[R][C][0], dp[R][C][1]);
    ans = max(ans, dp[R][C][2]);
    ans = max(ans, dp[R][C][3]);
    cout << ans;
    return 0;
}

Measured memory_bytes: 355520
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import           Control.Monad
import qualified Data.ByteString.Char8     as C8
import           Data.Bool
import           Data.Maybe

main :: IO ()
main = do
  [[x],[a],[b]] <- replicateM 3 readInts
  print . showAnswer $ solve (x,a,b)

type Input  = (Int, Int, Int)
type Output = Int

solve :: Input -> Output
solve (x,a,b) = (x-a) `mod` b

showAnswer :: Output -> Answer
showAnswer = Number

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | String String
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)    = bool "No" "Yes" b
  show (YESNO b)    = bool "NO" "YES" b
  show (AB b)       = bool "B"  "A" b
  show (Number i)   = show i
  show (String s)   = s
  show (Compare o)  = ordering "<" "=" ">" o
  show (Compare2 o) = ordering "Right" "Balanced" "Left" o

ordering :: a -> a -> a -> Ordering -> a
ordering lt eq gt o = case o of
  LT -> lt
  EQ -> eq
  GT -> gt

Measured memory_bytes: 380
#include <bits/stdc++.h>
#include <variant>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin>>n;
  vecll v(n+2);
  REP(i,n)cin>>v[i];
  constexpr ll INF = 1e15;
  int offset = 2;
  vector<vecll> dp(3, vecll(n+3*offset, -INF));
  dp[0][0] = 0;
  REP(i,n+2) {
    REP(j,3) {
      dp[j][i+offset] = max(dp[j][i+offset], dp[j][i] + v[i]);
      if (j < 2) dp[j+1][i+offset+1] = max(dp[j+1][i+offset+1], dp[j][i] + v[i+1]);
      if (j < 1) dp[j+2][i+offset+2] = max(dp[j+2][i+offset+2], dp[j][i] + v[i+2]);
    }
  }
  ll ans = dp[1+n%2][n+1+offset];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11084
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


DIV = 998244353

def main():
    N = iRaw()
    As = isRaw()
    Bs = isRaw()
    BAs = list(zip(Bs,As))
    BAs.sort()
    AIs = [[ba[1],idx] for idx,ba in enumerate(BAs)]
    AIs.sort()
    sAidx = [0]*len(AIs)
    for sIdx,ai in enumerate(AIs):
        a,idx = ai
        if a>BAs[sIdx][0]:
            return "No"
        sAidx[idx]=sIdx
    cycleSize = 0
    curIdx = 0
    visited = [0]*len(AIs)
    while visited[curIdx]==0:
        visited[curIdx]=1
        cycleSize +=1
        curIdx = sAidx[curIdx]
    if cycleSize < N:
        return "Yes"

    for idx in range(N-1):
        if AIs[idx+1][0]<=BAs[idx][0]:
            return "Yes"
    return "No"

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


Measured memory_bytes: 90896
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;
long long dp[2005][2005];

long long comb(int n,int r)
{
    if(dp[n][r]!=0) return dp[n][r];
    if(r==1) {
        return dp[n][r]=n;
    }
    if(r==n || r==0) {
        return dp[n][r]=1;
    }

    return dp[n][r]=(comb(n-1,r-1)%mod)+(comb(n-1,r)%mod)%mod;
}

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

    long long x,y;
    for(int i=1;i<=k;i++){
        int r=n-k-i+1;
        if(r<0) {
            cout << 0 <<endl;
            continue;
        }
        x=comb(n-k+1,i);
        x%=mod;
        y=comb(k-1,i-1);
        y%=mod;

        cout << (x*y)%mod <<endl;
    }

    return 0;
}


Measured memory_bytes: 29696
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<pair <int,int>>it(N);
    for (int i = 0; i < N; i++)
    {
        cin >> it[i].second >> it[i].first;
    }
    sort(it.begin(), it.end());
    int sum = 0;
    for(auto &itr : it){
        sum += itr.second;
        if(sum > itr.first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

#define ft first
#define sd second
#define sz(x) ((int)x.size())

using namespace std;

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

const int D = 1000 * 1000 * 1000 + 7, MAXN = 2 * 100 * 1000 + 123;


void multi(int& x, int y) { x = (ll)x * y % D; }
int inv(int x) {
	int res = 1;
	for (int i = D - 2; i; i >>= 1, x = (ll)x * x % D)
		if (i & 1)
			res = (ll)res * x % D;
	return res;
}

int r, c, a, b, ans, jav, fact[MAXN];


int main() {
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++)
		fact[i] = (ll)fact[i - 1] * i % D;
	cin >> r >> c >> a >> b;
	for (int i = 0; i < r - a; i++) {
		jav = fact[b + i - 1];
		multi(jav, inv(fact[b - 1]));
		multi(jav, inv(fact[i]));
		multi(jav, fact[r - i + c - b - 2]);
		multi(jav, inv(fact[r - i - 1]));
		multi(jav, inv(fact[c - b - 1]));
		ans += jav;
		ans %= D;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
n=int(input())
s1=list(input())
s2=list(input())
ans=0
if s1[0]==s2[0]:
    ans=3
else:
    ans=6
for i in range(n-1):
    if s1[i]==s2[i]:
        ans*=2
    else:
        if s1[i]==s1[i+1]:
            continue
        else:
            if s1[i+1]!=s2[i+1]:
                ans*=3
            else:
                ans*=1
print(ans%1000000007)

Measured memory_bytes: 9004
#include <bits/stdc++.h>
using namespace std;
int n; double p[2999] , dp[2999][1500];
double f( int i = 0 , int t = 0 )
{
    if( t == n/2+1 )
        return 0;
    if( i == n )
        return 1;
    double &d = dp[i][t];
    if ( d != -1 ) 
        return d;
    return d = f(i+1,t)*p[i] + f(i+1,t+1)*(1-p[i]);
}
int main()
{
    for(int i=0;i<2999;++i)
        for(int j=0;j<1500;++j)
            dp[i][j] = -1;
    cin >> n;
    for(int i=0;i<n;++i)
        cin >> p[i];
    cout << setprecision(9) << fixed << f();
}

Measured memory_bytes: 35584
from scipy.sparse.csgraph import floyd_warshall as fw

def main():
    h, w = map(int, input().split())
    link = [list(map(int, input().split())) for i in range(10)]

    a = [list(map(int, input().split())) for i in range(h)]

    link = fw(link)

    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] != -1:
                ans += link[a[i][j]][1]
    print(int(ans))

if __name__ == "__main__":
    main()

Measured memory_bytes: 17732
import sys

def main():
    input = sys.stdin.readline
    s = [str(c) for c in input().strip()]
    t = [str(c) for c in input().strip()]

    s = sorted(s)
    t = sorted(t)[::-1]

    S = ''
    for c in s:
        S += c
    T = ''
    for c in t:
        T += c

    if S < T:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064