akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
class finite_field {
  const int md;
  const int sz;
  vector<int> fct, fnv;
  void init () {
    if (sz) {
      fct[0] = 1;
      for (int i = 1; i < sz; i++) fct[i] = prod(fct[i - 1], i);
      fnv[sz - 1] = inv(fct[sz - 1]);
      for (int i = sz - 1; i >= 1; i--) fnv[i - 1] = prod(fnv[i], i);
    }
  }
  public:
    finite_field(
        const int md,
        const int init_factorial_size = 0,
        const int init_power_size = 0
      ) :
      md(md), sz(init_factorial_size),
      fct(sz), fnv(sz)
      {
        init();
      }
    inline void add (int& a, const int b) const {
      a += b;
      if (a >= md) a -= md;
    }
    inline void sub (int& a, const int b) const {
      a -= b;
      if (a < 0) a += md;
    }
    template<class... A> inline int sum (A... args) const {
      int ret = 0;
      for (int a : initializer_list<int>{args...}) {
        add(ret, a);
      }
      return ret;
    }
    inline int dif (int a, int b) const {
      sub(a, b);
      return a;
    }
    // inline int prod (int a, int b) const {
    //   return (long long)a * b % md;
    // }
    template<class... A> inline int prod (A... args) const {
      long long ret = 1;
      for (int a : initializer_list<int>{args...}) {
        ret *= a;
        ret %= md;
      }
      return (int)ret;
    }
    void mul (int& a, int b) const {
      a = prod(a, b);
    }
    inline int inv (int a) const {
      a %= md; if (a < 0) a += md;
      int b = md, u = 0, v = 1;
      while (a) {
        int t = b / a;
        b -= a * t; swap(a, b);
        u -= v * t; swap(u, v);
      }
      assert(b == 1);
      if(u < 0) u += md;
      return u;
    }
    inline int quat (int a, int b) const {
      return prod(a, inv(b));
    }
    inline void div (int& a, int b) const {
      a = quat(a, b);
    }
    inline int pow (int a, long long b) {
      int ret = 1;
      for (; b; b >>= 1) {
        if (b & 1) mul(ret, a);
        a = prod(a, a);
      }
      return ret;
    }
    inline int binom (int n, int k) const {
      assert(0 <= n && n < sz);
      if (k < 0 || n < k) return 0;
      return prod(fct[n], fnv[k], fnv[n - k]);
    }
};
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<vector<int>> dp(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = a[i] > a[j] ? 1 : 0;
    }
  }
  finite_field fld(1e9 + 7);
  int inv2 = fld.inv(2);
  int coeff = fld.pow(2, q);
  while (q--) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    auto half = [&] (int& a, int& b) -> void {
      fld.add(a, b);
      a = b = fld.prod(a, inv2);
    };
    half(dp[x][y], dp[y][x]);
    for (int z = 0; z < n; z++) if (z != x && z != y) {
      half(dp[x][z], dp[y][z]);
      half(dp[z][x], dp[z][y]);
    }
  }
  int ret = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      fld.mul(dp[i][j], coeff);
      fld.add(ret, dp[i][j]);
    }
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 37776
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int w, a, b;
	cin >> w >> a >> b;
	cout << ((a == b) || (a < b && a + w >= b) || (b < a && b + w >= a) ? 0 : min(abs(b - a - w), abs(a - b - w))) << endl;
	return 0;
}

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

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> S(13, 0), H(13, 0), C(13, 0), D(13, 0);

    for(int i = 0; i < N; i++){
        char c;
        int v;
        cin >> c >> v;
        switch(c){
            case 'S': S.at(v-1) = 1; break;
            case 'H': H.at(v-1) = 1; break;
            case 'C': C.at(v-1) = 1; break;
            case 'D': D.at(v-1) = 1; break;
        }
    }
    
    for(int i = 0; i < S.size(); i++){
        if(S.at(i) == 0) cout << "S " << (i+1) << endl;
    }
    for(int i = 0; i < H.size(); i++){
        if(H.at(i) == 0) cout << "H " << (i+1) << endl;
    }
    for(int i = 0; i < C.size(); i++){
        if(C.at(i) == 0) cout << "C " << (i+1) << endl;
    }
    for(int i = 0; i < D.size(); i++){
        if(D.at(i) == 0) cout << "D " << (i+1) << endl;
    }
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
long double EPS=1E-8;
////////////////////////////////////////

ll cal(l_l a,l_l b){
    return abs(a.first-b.first)+abs(a.second-b.second);
}

int main(){
    ll h,w,d;cin>>h>>w>>d;
    ll a[h][w];
    rep(i,0,h-1)rep(j,0,w-1){cin>>a[i][j];a[i][j]--;}
    ll n=h*w;
    l_l pos[n];
    rep(i,0,h-1)rep(j,0,w-1){
        pos[a[i][j]]=l_l(i,j);
    }
    vector<ll>v[d];
    rep(i,0,d-1){
        l_l last=pos[i];
        ll sum=0;
        for(ll j=0;;j++){
            ll k=i+j*d;
            if(k>=n)break;
            sum+=cal(last,pos[k]);
            last=pos[k];
            v[i].pb(sum);
        }
    }
    ll q;cin>>q;
    /*rep(i,0,d-1){
        for(auto x:v[i]){
            cout<<x<<" ";
        }cout<<endl;
    }*/
    while(q--){
        ll l,r;cin>>l>>r;l--;r--;
        ll c=l%d;
        ll e=(l-c)/d,f=(r-c)/d;
        cout<<v[c][f]-v[c][e]<<endl;
    }
    return 0;
}




Measured memory_bytes: 7424
import sys
input = sys.stdin.readline

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


SA, SB = [0]*(N+1), [0]*(M+1)
for i, a in enumerate(A):
    SA[i + 1] = SA[i] + a

for i, b in enumerate(B):
    SB[i + 1] = SB[i] + b

piv = M
ans = 0
flg = False
for i, a in enumerate(SA):
    while SB[piv] + SA[i] > K:
        piv -= 1
        if piv < 0:
            flg = True
            break
    if flg:
        break
    ans = max(ans, piv+i)
print(ans)


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

using namespace std;

int main(int argc, char const *argv[]) {
  int ans = 0;
  char s[4];
  for (size_t i = 0; i < 4; i++) {
    cin >> s[i];
    if (s[i] == '+') ans++;
    else ans--;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define N 200000
#define INT(X) \
  ( *( (const int *)(X) ) )

int pc = 0;
int pv[ N + 1 ] = { 1, 1, 0 };

int compare (
  const void  * a,
  const void  * b
  )
{
  return ( INT( a ) - INT( b ) );
}

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int i, j;

  for ( j = 2; j <= N; ++j )
  {
    if ( pv[ j ] ) continue ;

    for ( i = j * 2; i <= N; i += j )
    {
      pv[ i ] = 1;
    }
  }
  for ( i = 2; i <= N; ++i )
  {
    if ( !pv[ i ] )
    {
      pv[ pc++ ] = i;
    }
  }

  for ( ; ; )
  {
    int d[ 5050 ], dc = 0;
    int n, p, b;

    scanf ( "%d%d", &n, &p );
    if ( !~( n & p ) ) break ;

    for ( b = 0; pv[ b ] <= n; ++b ) ;

    for ( j = 0; j < 100; ++j )
    for ( i = j; i < 100; ++i )
    {
      d[ dc++ ] = pv[ b + j ] + pv[ b + i ];
    }
    qsort ( d, dc, sizeof ( int ), compare );

    printf ( "%d\n", d[ p - 1 ] );
  }

  return ( 0 );
}

Measured memory_bytes: 1312
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <iomanip>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)

using namespace std;

int main(){
	int i,j;
	double A,B,H,M;
	double tx,ty,mx,my;
	double PI = 3.1415926535897932384626433832795028841971 ;
	cin >> A >> B >> H >> M;

	double trad = 2.*PI*(H/12.+ (M/60.)/12.);
	double mrad = 2.*PI*(M/60.);
	double ans;
	if(trad-mrad <= PI)ans = A*A + B*B - 2.*A*B*cos(trad-mrad);
	else ans = A*A + B*B - 2.*A*B*cos(2*PI - (trad-mrad));
	cout<< setprecision(10)<< pow(ans,0.5) << endl;
	return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct UnionFind{
  vector<ll> par,siz;
  
  UnionFind(ll N):par(N+1),siz(N+1,1){
    for(int i=0; i<=N; i++)
      par[i]=i;
  }
  
  ll root(ll x){
    if(par[x]==x)
      return x;
    return par[x]=root(par[x]);
  }
  
  void unite(ll x, ll y){
    ll rx=root(x), ry=root(y);
    if(rx==ry)
      return;
    par[ry]=rx;
    siz[rx]+=siz[ry];    
  }
  
  ll size(ll x){
    return siz[root(x)];
  }
};

int main(){
  ll N,M;
  cin>>N>>M;
  vector<ll> A(M,0), B(M,0), ans(M,0);
  for(int i=0; i<M; i++){
    ll a,b;
    cin>>a>>b;
    A[i]=a;
    B[i]=b;
  }
  UnionFind tree(N);
  ll all=N*(N-1)/2;
  for(int i=M-1; i>=0; i--){
    ans[i]=all;
    if(tree.root(A[i])==tree.root(B[i]))
       continue;
    all-=tree.size(A[i])*tree.size(B[i]);
    tree.unite(A[i],B[i]);
  }
  for(int i=0; i<M; i++)
    cout<<ans[i]<<endl;
}


Measured memory_bytes: 5248
import sys
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.append((x, y))
            seen[y][x] = True



dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
while todo:
    for _ in range(len(todo)):
        x, y = todo.popleft()
        #print(x, y)
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))
    # cnt += 1

#print(seen)
# print(route)
M = 0
for y in range(H):
    for x in range(W):
        M = max(M, route[y][x])
print(M)

Measured memory_bytes: 95580
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
	int N;
	cin >> N;
	unordered_map<string, int> hist;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;

		std::sort(s.begin(), s.end());
		bool found = false;
		auto it = hist.find(s);

		if (it != hist.end())
		{
			(*it).second++;
		}
		else
		{
			hist.insert(pair<string, int>(s, 1));
		}
	}

	unsigned long long int ans = 0;
	for (auto && i : hist)
	{
		unsigned long long int c = i.second;
		ans += c * (c - 1) / 2;
	}

	cout << ans << endl;

	return 0;
}

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

using ll = long long;

int main()
{
    cout << fixed << setprecision(6);

    int N, A, B; cin >> N >> A >> B;

    auto values = vector<ll>(N);
    for (auto& x : values) cin >> x;
    sort(begin(values), end(values));
    reverse(begin(values), end(values));

    auto binomial = new ll[51][51]{};
    binomial[0][0] = 1;
    for (auto n = 1; n <= N; n++)
        for (auto k = 0; k <= n; k++)
            binomial[n][k] = k == 0 ? 1 : binomial[n-1][k] + binomial[n-1][k-1];

    const auto max_average = accumulate(begin(values), begin(values)+A, 0.0) / A;
    cout << max_average << endl;

    const auto count = std::count(begin(values), end(values), values[A-1]);
    if (values[0] == values[A-1])
    {
        auto ways = 0LL;
        for (auto k = A; k <= B; k++)
            ways += binomial[count][k];
        cout << ways << endl;
    }
    else
    {
        const auto first = int(find(begin(values), end(values), values[A-1]) - begin(values));
        cout << binomial[count][A-first] << endl;
    }
}


Measured memory_bytes: 256
n = gets.chomp.to_i
n_length = n.to_s.length

def sum_odd_digits(odd_digits)
    sum = 0
    while odd_digits > 0 do
        sum += 9*(10**(odd_digits-1))
        odd_digits -= 2
    end
    sum
end

if n_length % 2 == 0
    puts sum_odd_digits(n_length-1)
else
    max_digits_sum = n-10**(n_length-1) +1
    puts max_digits_sum + sum_odd_digits(n_length-2)
end


Measured memory_bytes: 1788
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print(max(dp[i][~i]for i in range(n+1)))

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 2e5 + 3;
int N;
int A[MC];

int main(){
	cin >> N;
	repp(i,0,N) cin >> A[i];
	sort(A,A+N);
	int ans = 0;
	int k = N-1;
	repm(t,30,0){
		int i = 0;
		while(k >= 0 && (A[k] >= (1<<(t-1)) || A[k] < 0)){
			if(A[k] < 0){
				--k;
				continue;
			}
			while(i < k && (A[k] + A[i] < (1<<t) || A[i] < 0)) ++i;
			if(i < k && A[k] + A[i] == (1<<t)){
				A[i] = A[k] = -1;
				++i;
				++ans;
			}
			--k;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << #x << " = " << (x) << "\n";
using ll = long long;
using ld = long double;

static const auto do_fast_io = [] {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

/*
 * There are two approaches to understand this logic,
 *
 * * First
 * - https://codeforces.com/blog/entry/64250?#comment-482888 along with
 * - https://codeforces.com/blog/entry/64250?#comment-482888
 *
 * * Second
 * - https://codeforces.com/blog/entry/64250?#comment-482841 along with
 * - https://codeforces.com/blog/entry/64250?#comment-483017
 */

int main() {
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == 1) {
            ++c1;
        } else if (x == 2) {
            ++c2;
        } else {
            ++c3;
        }
    }

    double dp[n + 1][n + 1][n + 1] = {0};

    for (int i = 0; i <= c3; ++i) {
        // i is number of dishes having 3 sushi
        for (int j = 0; i + j <= c2 + c3; ++j) {
            // j is number of dishes having 2 sushi
            for (int k = 0; i + j + k <= c1 + c2 + c3; ++k) {
                // k is number of dishes having 1 sushi
                if (not i and not j and not k) {
                    continue;
                }
                int non_empty_dishes = i + j + k;
                double pi =
                    i / double(non_empty_dishes);  // probablity pi, of chosing
                                                   // dish with 3 sushi
                double pj =
                    j / double(non_empty_dishes);  // probablity pj, of chosing
                                                   // dish with 2 sushi
                double pk =
                    k / double(non_empty_dishes);  // probablity pk, of chosing
                                                   // dish with 1 sushi
                double pe =
                    n / double(non_empty_dishes);  // probablity pe, of chosing
                                                   // an empty dish
                if (i) {
                    dp[i][j][k] += dp[i - 1][j + 1][k] * pi;
                }
                if (j) {
                    dp[i][j][k] += dp[i][j - 1][k + 1] * pj;
                }
                if (k) {
                    dp[i][j][k] += dp[i][j][k - 1] * pk;
                }
                dp[i][j][k] += pe;
            }
        }
    }
    cout << fixed << setprecision(10) << dp[c3][c2][c1] << endl;
    return 0;
}


Measured memory_bytes: 213376
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main()
    {
        //var NN = ReadLine().Split().Select(int.Parse).ToArray();
        var b = ReadLine();

        switch (b)
        {
            case "A":
                WriteLine("T");
                break;
            case "T":
                WriteLine("A");
                break;
            case "C":
                WriteLine("G");
                break;
            case "G":
                WriteLine("C");
                break;
            default:
                break;
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pii;

int getScore(char a, char b, int R, int S, int P) {
  if (a == 'r' && b == 's') {
    return R;
  } else if (a == 's' && b == 'p') {
    return S;
  } else if (a == 'p' && b == 'r') {
    return P;
  }
  return 0;
}

int main() {
  int N, K, R, S, P;
  string T;
  cin >> N >> K >> R >> S >> P >> T;
  vector<vector<int>> dp(3, vector<int>(N));
  for (int i = 0; i < K; i++) {
    for (int j = i; j < N; j += K) {
      if (j < K) {
        dp[0][j] = getScore('r', T[j], R, S, P);
        dp[1][j] = getScore('s', T[j], R, S, P);
        dp[2][j] = getScore('p', T[j], R, S, P);
      } else {
        dp[0][j] = max(dp[1][j - K], dp[2][j - K]) + getScore('r', T[j], R, S, P);
        dp[1][j] = max(dp[0][j - K], dp[2][j - K]) + getScore('s', T[j], R, S, P);
        dp[2][j] = max(dp[0][j - K], dp[1][j - K]) + getScore('p', T[j], R, S, P);
      }
    }
  }
  int score = 0;
  for (int i = 1; i <= K && N - i >= 0; i++) {
    int temp = max(max(dp[0][N - i], dp[1][N - i]), dp[2][N - i]);
    score += temp;
  }
  cout << score << endl;
  return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n, w, i, j;
  cin>>n>>w;
  long long dp[n+1][w+1];
  long long wt[n];
  long long v[n];
  for(i=0;i<n;i++)
  {
    int w1, v1;
    cin>>w1>>v1;
    wt[i]=w1;
    v[i]=v1;
  }
  for(i=0;i<=n;i++)
  {
    for(j=0;j<=w;j++)
    {
      if(i==0)
        dp[i][j]=0;
      else if(j==0)
        dp[i][j]=0;
      else if(j<wt[i-1])
        dp[i][j]=dp[i-1][j];
      else
        dp[i][j]=max(dp[i-1][j], v[i-1]+dp[i-1][j-wt[i-1]]);   
    }
  }
  cout<<dp[n][w]<<endl;
  return 0;
}

Measured memory_bytes: 79104
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 */
public class Main {

	/** 道を表す文字 */
	private static final char ROAD = '.';

	/** 移動のX座標差分配列 */
	private static final int[] MOVE_XS = new int[] { 1, -1, 0, 0 };
	/** 移動のY座標差分配列 */
	private static final int[] MOVE_YS = new int[] { 0, 0, 1, -1 };
	/** ワープのX座標差分配列 */
	private static final int[] WARP_XS = new int[] { 1, 1, 1, 1, -1, -1, -1, -1, 2, 2, 2, 2, 2, -2, -2, -2, -2, -2, 0,
			0 };
	/** ワープのY座標差分配列 */
	private static final int[] WARP_YS = new int[] { 1, -1, 2, -2, 1, -1, 2, -2, 0, 1, -1, 2, -2, 0, 1, -1, 2, -2, 2,
			-2 };

	private static final int INF = Integer.MAX_VALUE >> 1;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int h = scanner.nextInt(), w = scanner.nextInt();
			int ch = scanner.nextInt() - 1, cw = scanner.nextInt() - 1;
			int dh = scanner.nextInt() - 1, dw = scanner.nextInt() - 1;
			boolean[][] road = new boolean[h][w];
			IntStream.range(0, h).forEach(i -> {
				char[] s = scanner.next().toCharArray();
				IntStream.range(0, w).forEach(j -> road[i][j] = (ROAD == s[j]));
			});
			int[][] dp = new int[h][w];
			IntStream.range(0, h).forEach(i -> Arrays.fill(dp[i], INF));
			setDp(dp, h, w, ch, cw, road);
			System.out.println((INF == dp[dh][dw]) ? -1 : dp[dh][dw]);
		}
	}

	/**
	 * 個々のマスに移動するための最小コストの配列の値をセットする
	 * 
	 * @param dp   個々のマスに移動するための最小コストの配列
	 * @param h    縦幅
	 * @param w    横幅
	 * @param ch   開始時点
	 * @param cw   開始時点
	 * @param road 道路を表す配列
	 */
	private static void setDp(int[][] dp, int h, int w, int ch, int cw, boolean[][] road) {

		dp[ch][cw] = 0;
		Queue<Masu> queue = new PriorityQueue<>();
		queue.add(new Masu(ch, cw, 0));
		while (!queue.isEmpty()) {
			Masu masu = queue.poll();
			int nx = masu.x, ny = masu.y;
			if (masu.cost == dp[nx][ny]) {
				// 移動
				for (int i = 0; i < MOVE_XS.length; i++) {
					int newX = nx + MOVE_XS[i], newY = ny + MOVE_YS[i];
					if ((newX >= 0) && (newX < h) && (newY >= 0) && (newY < w) && road[newX][newY]) {
						if (dp[newX][newY] > dp[nx][ny]) {
							dp[newX][newY] = dp[nx][ny];
							queue.add(new Masu(newX, newY, dp[newX][newY]));
						}
					}
				}
				// ワープ
				for (int i = 0; i < WARP_XS.length; i++) {
					int newX = nx + WARP_XS[i], newY = ny + WARP_YS[i];
					if ((newX >= 0) && (newX < h) && (newY >= 0) && (newY < w) && road[newX][newY]) {
						if (dp[newX][newY] > dp[nx][ny] + 1) {
							dp[newX][newY] = dp[nx][ny] + 1;
							queue.add(new Masu(newX, newY, dp[newX][newY]));
						}
					}
				}
			}
		}
	}

	/**
	 * マスを表すクラス
	 */
	private static class Masu implements Comparable<Masu> {
		/** X座標 */
		int x;
		/** Y座標 */
		int y;
		/** ワープ数 */
		int cost;

		/**
		 * コンストラクタ
		 * 
		 * @param x
		 * @param y
		 * @param cost
		 */
		Masu(int x, int y, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.cost = cost;
		}

		@Override
		public int compareTo(Masu masu) {
			return Integer.compare(cost, masu.cost);
		}
	}
}


Measured memory_bytes: 63216
//gcc -std=gnu11 -O2 -o a.out Main.c -lm

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//#define	dbgPrint	printf
#define	dbgPrint	

int main(void)
{
	
	int w, h, n;
	int x[100], y[100], a[100];
	int map[100][100];
	int ret, ans;
	int i, j, k;
	
	memset(map, 0, sizeof(map));
	ret = scanf("%d %d %d", &w, &h, &n);
	
	for(i = 0 ; i < n ; i++){
		ret = scanf("%d %d %d", &x[i], &y[i], &a[i]);
	}
	
	for(i = 0 ; i < n ; i++){
		dbgPrint("a[i]=%d\n", a[i]);
		
		ans = 0;
		for(j = 0 ; j < w ; j++){
			for(k = 0 ; k < h ; k++){
				if(map[j][k] == 0){
					ans++;
				}
			}
		}
		dbgPrint("ans=%d\n", ans);
		
		switch(a[i]){
			case 1:
				for(j = 0 ; j < x[i] ; j++){
					for(k = 0 ; k < h ; k++){
						map[j][k] = 1;
					}
				}
				break;
			case 2:
				for(j = x[i] ; j < w ; j++){
					for(k = 0 ; k < h ; k++){
						map[j][k] = 1;
					}
				}
				break;
			case 3:
				for(j = 0 ; j < w ; j++){
					for(k = 0 ; k < y[i] ; k++){
						map[j][k] = 1;
					}
				}
				break;
			case 4:
				for(j = 0 ; j < w ; j++){
					for(k = y[i] ; k < h ; k++){
						map[j][k] = 1;
					}
				}
				break;
		}
	}
	
	ans = 0;
	
	for(i = 0 ; i < w ; i++){
		for(j = 0 ; j < h ; j++){
			if(map[i][j] == 0){
				ans++;
			}
		}
	}
	printf("%d\n", ans);
	
	return 0;
}


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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7; 

string yn(bool f){return f?"yes":"no";}
string YN(bool f){return f?"YES":"NO";}

#define NUM 10

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	vector<int> c;
	vector<vector<vector<bool>>> dp;
	int N;
	
	cin>>N;
	
	c.resize(N);
	dp.resize(N, vector<vector<bool>>(N+1,vector<bool>(NUM,false)));
	
	for(int i = 0; i < N; i++){
		cin>>c[i];
	}
	
	for(int k = 1; k <= N; k++){
		for(int i = 0; i < N && i + k <= N; i++){
			int j = i + k;
			
			if(k == 1) dp[i][j][c[i]] = true;
			
			for(int l = i + 1; l < j; l++){
				for(int m = 0; m < NUM; m++){
					if(dp[i][l][0] && dp[l][j][0] || dp[i][l][m] && dp[l][j][m]) dp[i][j][0] = true;
					if(m && (dp[i][l][0] && dp[l][j][m] || dp[i][l][m] && dp[l][j][0] ||  dp[i][l][m] && dp[l][j][m])) dp[i][j][m] = true;
				}
			}
		}
	}
	
	cout<<yn(dp[0][N][0])<<endl;
	
	return 0;
}


Measured memory_bytes: 3916
/***************************************** 
****       Solution by SlavicG        ****
*****************************************/
 
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm> 
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;++i)
#define MX 10000000001
#define pow2(a) ((a)*(a))
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define endl "\n"
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 int longestIncreasingSubsequenceLenghtDP(int a[],int n){
    int dp[n],ans=0;
    for(int k = 0;k<n;k++){
        dp[k] = 1;
        for(int i = 0;i<k;i++){
            if(a[i] <= a[k]){
                dp[k] = max(dp[k],dp[i] + 1);
                ans = max(dp[k],ans);
            }
        }
    }
    return ans;
 }
int result[1000] = {0};
int factDP(int n) 
{
   if (n >= 0) {
      result[0] = 1;
      for (int i = 1; i <= n; ++i) {
         result[i] = i * result[i - 1];
      }
      return result[n];
   }
}
bool checkPrime(int n)
{
    if(n<2) return false;
    for(int x = 2;x*x <=n;x++)
    {
        if(n%x == 0)return false;
    }
    return true;
}
vector<int> primeFactors(int n){
    vector<int> f;
    for(int x = 2;x*x<=n;x++){
        while(n%x==0){
            f.push_back(x);
            n/=x;
        }
    }
    if(n>1)f.push_back(n);
    return f;
}
int binary_Search_Classic(int n, int arr[],int target){
	int l,r,mid;
	l=0;
	r=n-1;
	while(l<=r){
		mid= l+(r-l)/2;
		if(arr[mid] == target){
			return mid;
		}
		if(arr[mid] < target){
			l=mid+1;
		}else
		{
			r=mid-1;
		}
	}
	return -1;
}
int binary_Search_First_Greater(int n, int arr[],int target){
	int l,r,ans,mid;
	l = 0;
	r = n-1;
	ans=-1;
	while(l<=r){
		mid = l + (r-l)/2;
		if(arr[mid] > target){
			ans=mid;
			r=mid-1;
		}else{
			l = mid+1;
		}
	}
	return ans;
}
int countDistinctCharsString(string s) {
    unordered_map<char, int> m; 
    for (int i = 0; i < s.length(); i++) { 
        m[s[i]]++; 
    }
    return m.size(); 
} 
int main()
{
	int d,n;
	cin >> d >> n;
	int s= 1;
	while(d--)
	{
		s*=100;
	}
	if(n<=99)
	{
		cout << s * n << endl;
	}else{
		cout << s * 101 << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
#define M 1000000007

long fact[2000];
long factM[2000];

long pow(int n, int p)
{
  long result = 1;
  long nn = n;
  long pp = p;
  
  while (pp) {
    if (pp&1) result = (result * nn) % M;
    nn = (nn * nn) % M;
    pp >>= 1;
  }
  return result;
}

long combi(int n, int r)
{
  long result;
  
  if (n < r || r < 0) return 0;
  if (n == 0 && r == 0) return 1;
  result = (fact[n] * factM[r]) % M;
  result = (result * factM[n-r]) % M;
  return result;
}

int main()
{
    int n, k;
    cin >> n >> k;
  
    fact[0] = factM[0] = 1;
    for (int i = 1; i < 2000; i++) {
      fact[i] = (fact[i-1] * i) % M;
      factM[i] = (factM[i-1] * pow(i, M-2)) % M;
    }
    for (int i = 1; i <= k; i++) {
      cout << (combi(n-k+1, i) * combi(k-1, i-1)) % M << endl;
    }
    return 0;
}


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

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

	string ans = "Yes";
	map<char, char> mp1;
	rep(i, 0, t.size()) {
		if (mp1.count(t[i])) {
			if (mp1[t[i]] != s[i]) {
				ans = "No";
				break;
			}
		}
		else mp1[t[i]] = s[i];
	}
	map<char, char> mp2;
	rep(i, 0, s.size()) {
		if (mp2.count(s[i])) {
			if (mp2[s[i]] != t[i]) {
				ans = "No";
				break;
			}
		}
		else mp2[s[i]] = t[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define all( X ) ( X ).begin(), ( X ).end()

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	bool is_visited = false;
} node;
typedef struct {
	int to;
	int cost;
	P <int, int> change;
} edge;

int main(){
	ll N, M, K;
	cin >> N >> M >> K;
	vector <ll> A( N + 1 ), B( M + 1 );
	A[0] = 0;
	B[0] = 0;
	rep( i, 1, N+1 ){
		cin >> A[ i ];
		A[ i ] += A[ i - 1 ];
	}
	rep( i, 1, M+1 ){
		cin >> B[ i ];
		B[ i ] += B[ i - 1 ];
	}
	int maximum = 0;
	int index = M;
	rep( i, 0, N+1 ){
		if (A[i] + B[index] <= K){
			maximum = max(maximum, i+index);
		}
		bool can = false;
		rep_d(j, index+1, 0){
			if (A[i] + B[j] <= K){
				index = j;
				can = true;
				maximum = max(maximum, i+j);
				break;
			}
		}
		if (!can)
			break;
	}
	cout << maximum << endl;
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 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;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


Measured memory_bytes: 6400
use std::vec::Vec;
use std::cmp::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
  let (n, m): (usize, usize) = {
    let v = read_vec();
    (v[0], v[1])
  };

  let mut v: Vec<(i64, i64, i64)> = Vec::new();

  for _ in 0..n {
    let t = {
      let v: Vec<i64> = read_vec();
      (v[0], v[1], v[2])
    };
    v.push(t);
  }
  let xs: [i64; 2] = [1, -1];
  let mut ans: i64 = std::i64::MIN;
  for &i in &xs {
    for &j in &xs {
      for &k in &xs {
        ans = max(solve(m, i, j, k, &v), ans);
      }
    }
  }
  println!("{}", ans);
}


fn solve(m: usize, x: i64, y: i64, z: i64, v: &Vec<(i64, i64, i64)>) -> i64 {
  let mut x: Vec<i64> = v.iter().map(|e| e.0 * x + e.1 * y + e.2 * z).collect();
  x.sort_by(|a, b| b.cmp(&a));
  x.iter().take(m).sum::<i64>()
}


Measured memory_bytes: 4352
N,K = map(int,input().split())

a = list(map(int,input().split()))
ans = N

q = 0

a.sort()
a.reverse()
nmax = 0

for i in range(N):

    q += 1
    
    if nmax + a[i] >= K:
        ans -= q
        q = 0

    else:
        nmax = nmax + a[i]

print (ans)


Measured memory_bytes: 39408
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

def ch_2(n):
	# print(n)
	return n*(n-1)/2

count=Counter(A)

ans=0
for i in count.values():
	ans+=ch_2(i)

for j in range(N):
	ttl=ans
	ttl-=ch_2(count[A[j]])
	ttl+=ch_2(count[A[j]]-1)
	print(int(ttl))







Measured memory_bytes: 26780
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <numeric>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << std::endl; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << val << ' ';
            return *this;
        }
    };

public:
    output() : cout(std::cout)
    {
        cout << std::fixed << std::setprecision(15);
    }

    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val << ' ';
        return {};
    }
};

int main()
{
    input in;
    output out;

    std::size_t N = in.read<std::size_t>();

    std::vector<std::uint64_t> d(N);
    in.read(d.begin(), N);

    auto all = std::accumulate(std::begin(d), std::end(d), std::uint64_t{0}, std::bit_xor<>{});

    std::size_t rank = 0;
    for (std::uint64_t i = std::uint64_t{1} << 60; i != 0; i >>= 1) {
        if (all & i) continue;

        for (std::size_t r = rank; r < N; ++r) {
            if (!(d[r] & i)) continue;

            for (std::size_t rr = 0; rr < N; ++rr) {
                if (rr == r) continue;
                if (!(d[rr] & i)) continue;
                d[rr] ^= d[r];
            }
            std::swap(d[rank], d[r]);
            rank++;
            break;
        }
    }
    std::uint64_t res = 0;
    for (auto x : d) {
        res ^= x;
    }

    out << (res & (~all)) * 2 + all;

    return 0;
}


Measured memory_bytes: 1024
while 1:
    n=int(raw_input())
    if n==0:
        break
    field=[raw_input() for i in range(n)]
    large=[[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n):
            if field[i][j]=='.':
                large[i][j]=min(large[i][j-1],large[i-1][j],large[i-1][j-1])+1
    print max(map(max,large))

Measured memory_bytes: 35056
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FS r = new FS();
		int N = r.nextInt();
		long[] T = new long[N];
		long[] A = new long[N];
		for(int i=0; i<N; i++) {
			T[i] = r.nextLong();
			A[i] = r.nextLong();
		}
		for(int i=1; i<N; i++) {
			if(T[i-1]<=T[i] && A[i-1]<=A[i]) {
				continue;
			}
			Long rate = Math.max(T[i-1]/T[i], A[i-1]/A[i]);
			if(T[i-1]>T[i]*rate || A[i-1]>A[i]*rate) rate++;
			T[i] = T[i]*rate;
			A[i] = A[i]*rate;
		}
		System.out.println(T[N-1]+A[N-1]);
	}

	// Read Class
	static class FS {
		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() { return hasNextByte() ? buffer[ptr++] : -1;}
		private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
		private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}

		public boolean hasNext() { skipUnprintable(); 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 int nextInt() {
			return (int)nextLong();
		}
		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();
			}
		}
	}
}

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


//defines...
#define ll long long
#define tata return;
#define pb push_back
#define mp make_pair
#define in insert
#define run ios_base::sync_with_stdio(false);cin.tie(NULL);
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define vec vector<ll>
#define setl set<ll>
#define mapl map<ll,ll>
#define shunno cout<<0<<endl;
#define pi 2*acos(0.0)1
#define hobena cout<<-1<<endl;
ll n,m;
vec v[2000000];
ll dis[20000000];
setl s;
void dfs(ll x)
{
    ll i;
    dis[x]=1;
    for(i=0;i<v[x].size();i++)
    {
        if(dis[v[x][i]]==0){
        dis[v[x][i]]=1;
        s.in(v[x][i]);
        dfs(v[x][i]);
        }
    }
}








void oka()
{

        cin>>n>>m;
        ll i,j,k,a,b,ans=0;
        for(i=0;i<m;i++)
        {
            cin>>a>>b;
            v[a].pb(b);
            v[b].pb(a);
        }
        for(i=1;i<=n;i++)
        {
            if(dis[i]==0)
            {
                dfs(i);
                k=s.size();
                ans=max(ans,k);
                s.clear();


            }

        }
        cout<<min(ans+1,n)<<endl;








}






int main()
{
   //string g="abcd";
    //g.erase(g.begin()+3);
    //cout<<g<<endl;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    run
    ll i,t;
    t=1;
   //cin>>t;


    for(i=1;i<=t;i++)
    {


    oka();
    }






}


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

using ll=long long;
using namespace std;

int main(){
    string s;
    cin>>s;
    
    size_t l=s.length();
    int maxcnt=0;
    int cnt=0;
    rep(i,l){
        if(s[i]!='A' && s[i]!='C' && s[i]!='G' && s[i]!='T'){
            cnt=0;
            continue;
        }else cnt++;
        maxcnt=max(maxcnt,cnt);
    }
    
    cout<<maxcnt<<endl;
    return 0;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
#define nl '\n'
 
#define y1 aza_ibagaliev
 
#define f first
#define s second
	
#define ed end()
#define bg begin()
#define rbg rbegin()
 
#define rv reverse
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define ppf pop_front
 
#define sz size()
#define all(x) x.bg, x.ed
 
#define pll pair < ll, ll >
#define pii pair < int, int >
 
#define sqr(x) ((x) * 1ll * (x))
#define sqrd(x) ((x) * 1.0 * (x))
 
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
#define rnl cout << "----------------------------------------" << nl
 
#define bit __builtin_popcount
 
inline ll bip(ll x, ll n, ll mod){ll res=1;while(n){if(n & 1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}
        	
const int ppr = 257;
const ll INF = 2e18;
const int inf = 2e9;
const int mod = 1e9 + 7;
const int N = 1e5 + 123;
const ld pi = 3.1741592653589793238462643;
 
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int n, a[3004];
ll dp[3004][3004], p[3004];
bool u[3004][3004];

ll rec(int l, int r) {
	if(u[l][r]) return dp[l][r];
	u[l][r] = 1;
	if(l == r) return dp[l][r] = a[l];
	ll s = p[r] - p[l - 1];
	return dp[l][r] = max(s - rec(l + 1, r), s - rec(l, r - 1));
}

main() {             	
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);

//	srand(time(NULL));

	scanf("%d", &n);
  
    ll sum=0;

    for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]), p[i] = p[i - 1] + a[i];

	cout << 2 * rec(1, n) - p[n];

    return 0;                                        
}

Measured memory_bytes: 78464
#include <stdio.h>
 #include <string.h>
 char s[101];
 int main(void) {
 scanf("%s", s);
 int res = 0;
 int n = strlen(s);
 for (int i = 0; i < n; i++) {
 if (s[i] != s[n - 1 - i]) res++;
 }
 printf("%d\n", res / 2);
 }


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, D;
  cin >> N >> D;
  vector<vector<int>> X(N, vector<int>(D));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < D; j++){
      cin >> X.at(i).at(j);
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      int dis2 = 0;
      for (int k = 0; k < D; k++){
        dis2 += pow(X.at(i).at(k) - X.at(j).at(k), 2);
      }
      for (int k = 1; k < 401; k++){
        if (dis2 == pow(k, 2)){
          ans++;
        }
      }
    }
  }
  ans /= 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
N = int(input())
a = list(map(int,input().split()))

import collections
c = collections.Counter(a)
ans = 0

if len(c) == 1:
  ans = list(c.values())[0]
else:
  for x in range(min(a),max(a)):
    ans_candidate = c[x] + c[x+1] + c[x+2]

    if ans < ans_candidate:
      ans = ans_candidate
print(ans)


Measured memory_bytes: 14436
import sys

sys.setrecursionlimit(10**9)

def dfs(num,lis,count,target):
    visited[num]=count
    n_city=A[num]
    if visited[n_city]!=-1:
        lis.append(num)
        if target<=count:
              print(lis[target]+1)
        else:
            rep=len(lis)-visited[n_city]
            target-=visited[n_city]
            amari=target%rep
            temp=lis[visited[n_city]:]
            print(temp[amari]+1)
        exit()
    else:
        lis.append(num)
        dfs(n_city,lis,count+1,target)
    

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=list(map(lambda x:x-1,A))

visited=[-1]*N

dfs(0,[],0,K)

Measured memory_bytes: 266016
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;
const ll INF = 100100100100100100;

ll N;
ll a[100100];
int main(){
  cin >> N;
  ll mem = -1;
  rep(i,N){
    ll b;
    cin >> b;
    a[b]++;
  }
  ll cnt = 0;
  ll pa = 0;
  ll pb = 0;
  rep(i,100010){
    if(a[i] > 0){
      cnt++;
      if(cnt == 1){
        pa = i;
      }
      if(cnt == 2){
        pb = i;
      }
    }
  }
  if(cnt > 2) cout << "No" << endl;
  if(cnt == 1){
    ll tmp = a[pa];
    if(tmp == pa+1 || tmp>= 2*pa){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
  else if(cnt == 2){
    ll ans = 0;
    ll tmpa = a[pa];
    ll tmpb = a[pb];
    if(tmpa >= pa+1){
      cerr << "aaa" << endl;
      cout << "No" << endl;
    }
    else{
      ans += tmpa;
      ans += (tmpb)/2;
      if(ans < pb){
        cerr << "bbb" << endl;
        cout << "No" << endl;
      }
      else{
        cerr << "ccc" << endl;
        cout << "Yes" << endl;
      }
    }
  }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;
#define INF 1000000007
#define MOD 1000000007
#define SEP " "

int		main(void)
{
	int n;
	cin >> n;
	vector<int> l(n);
	for (int i = 0; i < n; i++)
		cin >> l[i];
	sort(l.begin(), l.end());
	ll ans = 0;
	for (int i = 0; i < n - 2; i++)
	{
		for (int j = i + 1; j < n - 1; j++)
		{
			ans += lower_bound(l.begin(), l.end(), l[i] + l[j]) - lower_bound(l.begin() + j + 1, l.end(), l[j]);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
def main():
    from collections import deque

    K = int(input())
    if K <= 9:
        print(K)
        return
    
    q = deque()
    for i in range(1, 10):
        q.append(i)
    
    count = 9
    while True:
        get_num = q.popleft()
        for i in range(-1, 2):
            add_num = get_num % 10 + i
            if 0 <= add_num and add_num <= 9:
                q.append(get_num * 10 + add_num)
                count += 1
                if count == K:
                    print(q.pop())
                    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 12112
#include <stdio.h>

int main(){
    int arr[3][3];
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    
    int n;
    scanf("%d", &n);
    int input[n];
    for(int i = 0; i<n; i++){
        scanf("%d", &input[i]);
    }
    for(int i = 0; i<n; i++){
        for(int j = 0; j<3; j++){
            for(int k = 0; k<3; k++){
                if(input[i] == arr[j][k]){
                    arr[j][k] = 0;
                }
            }
        }
    }
    
    
    if((arr[0][0] == arr[0][1] && arr[0][1] == arr[0][2]) || (arr[1][0] == arr[1][1] && arr[1][0] == arr[1][2]) || (arr[2][0] == arr[2][1] && arr[2][0]== arr[2][2]) ||
    (arr[1][1] == arr[2][2] && arr[1][1]== arr[0][0]) || (arr[0][2] == arr[1][1] && arr[0][2] == arr[2][0]) || (arr[0][0] == arr[1][0] && arr[0][0] == arr[2][0]) ||
    (arr[0][1] == arr[1][1] && arr[0][1] == arr[2][1]) || (arr[0][2] == arr[1][2] && arr[0][2] == arr[2][2])){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 1612
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
  read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
  match n {
    0 => a,
    _ => {
      a.push(read::<T>());
      read_n_logic(n - 1, a)
    }
  }
}

use std::cmp::{max, min};
use std::collections::VecDeque;


fn main() {
  let n: usize = read();
  let m: usize = read();
  let m_vec: Vec<usize> = read_n(m);
  let nums = [10, 2, 5, 5, 4, 5, 6, 3, 7, 6];
  // [桁数, 最後の数]
  const INF: i32 = 1001001001;

  let nums = [10, 2, 5, 5, 4, 5, 6, 3, 7, 6];
  let mut dp = vec![-INF; n + 1];
  dp[0] = 0;
  for i in 1..n + 1 {
    for &a in &m_vec {
      if nums[a] <= i {
        dp[i] = std::cmp::max(dp[i], dp[i - nums[a]] + 1);
      }
    }
  }

  let mx = dp[n] as usize;

  let mut rem = n;
  let mut ans = vec![0; mx];
  for i in 0..mx {
    for &a in &m_vec {
      if rem >= nums[a] && dp[rem - nums[a]] == dp[rem] - 1 {
        ans[i] = std::cmp::max(ans[i], a);
      }
    }
    rem -= nums[ans[i]];
  }
  ans.sort_by_key(|&a| -(a as i32));


  // println!("{:?}", ans);
  for i in ans {
    print!("{}", i)
  }

  // for i in m_vec {
  //   dist.entry().or_insert(b);
  // }

}


Measured memory_bytes: 4352