akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n=int(readline())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

m = map(int,read().split())
XD = sorted(zip(m,m))
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
t=0
for x,d in reversed(XD):
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])

Measured memory_bytes: 108792
#include <time.h>

#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <numeric>

using namespace std;

int main() {
	int32_t n;
	cin>>n;
	int32_t *max_speed=new int32_t[n+2];
	int32_t *time=new int32_t[n+1];
	time[0]=0;
	for(int32_t i1=0;i1<n;i1++){
		int32_t temp;
		cin>>temp;
		time[i1+1]=time[i1]+temp;
	}
	max_speed[0]=0;
	max_speed[n+1]=0;
	for(int32_t i1=0;i1<n;i1++){
		cin>>max_speed[i1+1];
	}
	int32_t *forward_limit=new int32_t[n+1];
	forward_limit[0]=0;
	for(int32_t i1=1;i1<n+1;i1++){
		forward_limit[i1]=min(forward_limit[i1-1]+(time[i1]-time[i1-1]),max_speed[i1]/*,max_speed[i1+1]*/);
		forward_limit[i1]=min(forward_limit[i1],max_speed[i1+1]);
	}
	int32_t *backward_limit=new int32_t[n+1];
	backward_limit[n]=0;
	for(int32_t i1=n-1;i1>=0;i1--){
		backward_limit[i1]=min(backward_limit[i1+1]+(time[i1+1]-time[i1]),max_speed[i1]/*,max_speed[i1+1]*/);
		backward_limit[i1]=min(backward_limit[i1],max_speed[i1+1]);

	}
	double ans=0;
	for(int32_t i1=0;i1<n;i1++){
		int32_t left_limit=min(forward_limit[i1],backward_limit[i1]);
		int32_t right_limit=min(forward_limit[i1+1],backward_limit[i1+1]);
		if(left_limit==max_speed[i1+1]){
			if(right_limit==max_speed[i1+1]){
				ans+=max_speed[i1+1]*(time[i1+1]-time[i1]);
			}else{
				ans+=max_speed[i1+1]*(time[i1+1]-time[i1])-0.5*((max_speed[i1+1]-right_limit)*(max_speed[i1+1]-right_limit));
			}
		}else{
			if(right_limit==max_speed[i1+1]){
				ans+=max_speed[i1+1]*(time[i1+1]-time[i1])-0.5*((max_speed[i1+1]-left_limit)*(max_speed[i1+1]-left_limit));
			}else{
				if(2*max_speed[i1+1]-left_limit-right_limit<time[i1+1]-time[i1]){
					ans+=max_speed[i1+1]*(time[i1+1]-time[i1])-0.5*((max_speed[i1+1]-left_limit)*(max_speed[i1+1]-left_limit))-0.5*((max_speed[i1+1]-right_limit)*(max_speed[i1+1]-right_limit));
				}else{
					double peek_speed=(left_limit+right_limit)*0.5+(time[i1+1]-time[i1])*0.5;
					double peek_time=peek_speed-left_limit;
					ans+=(left_limit+peek_speed)*peek_time*0.5+(right_limit+peek_speed)*(time[i1+1]-time[i1]-peek_time)*0.5;
				}
			}
		}
	}
	cout<<fixed<<setprecision(8);
	cout<<ans<<endl;

}


Measured memory_bytes: 256
/*
AizuOnline A0519
Title Worst sport writer

*/
#include <stdio.h>
// Select Below
//#include <stdlib.h>
//#include <string.h>
//#include <float.h>
//#include <math.h>
//#include <limits.h>
//Global data section
#define SHOUGENNO 100000
#define NINZUU 5000
int n,m;
int x[SHOUGENNO],y[SHOUGENNO];
int flag[NINZUU+1];
//
void show()
{
  int i;
  for(i=1;i<=n;i++)
    printf("%d:",flag[i]);
  printf("\n");
}
main()
{
  int i,cnt,cnt2,multi;

  scanf("%d ",&n);
  scanf("%d ",&m);
  for(i=0;i<m;i++)
    scanf("%d %d",&x[i],&y[i]);
  for(i=0;i<n;i++)
    flag[i]=0;

  cnt=n;multi=0; 

  while(cnt>0)
    {
      for(i=1;i<=n;i++)
	if(flag[i]>0)
	  flag[i]=0;
      //show();
      for(i=0;i<m;i++)
	if(flag[x[i]]!=-1)
	  flag[y[i]]=1;
      cnt2=0;
      for(i=1;i<=n;i++)
	{
	  if(flag[i]==0)
	    {
	      printf("%d\n",i);
	      cnt--;
	      flag[i]=-1;
	      cnt2++;
	      if(cnt2>1)
		multi=1;
	    }
	}
      //show();
    }
  printf("%d\n",multi);  
  return(0);
}

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

using namespace std;
 
#define EPS 1e-6
#define INF 1e8
typedef complex<double> P;
 
double dot(P a,P b){
  return real(conj(a)*b);
}
 
double cross(P a,P b){
  return imag(conj(a)*b);
}
 
struct Point{
  double x,y;
};
 
int main(){
  double D;
 
  while(scanf("%lf",&D), D){
    Point v,p;
     
    scanf("%lf%lf%lf%lf",&p.x,&p.y,&v.x,&v.y);
    P np = P(p.x,p.y), nv = P(v.x,v.y);
    double dist = INF;
 
    if(abs(cross(np,nv)) < EPS){
      if(dot(np,nv) < -EPS){
        dist = abs(np);
      }else{
        dist = 2-abs(np);
      }
    }
    
    if(dist < D){
      printf("%.8f\n",dist);
    }else{
      printf("impossible\n");
    }
  }
  
  return 0;
}

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

using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;

    vector<vector<char>> s(H+2, vector<char>(W+2));
    for (int i = 0; i < H+2; i++) {
        for (int j = 0; j < W+2; j++) {
            if (i == 0 || i == H+1 || j == 0 || j == W+1) s[i][j] = '.';
            else cin >> s[i][j];
        }
    }

    bool flag = true;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (s[i][j] == '#') {
                if (s[i-1][j] == '.' && s[i+1][j] == '.' && s[i][j-1] == '.' && s[i][j+1] == '.') {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag) break;
    }

    cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) cout<<(#_v)<<":";for(auto(_x):(_v)){cout<<" "<<(_x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

class SCC {
private:
    const int n;
    vector<vector<int>> G;
    vector<vector<int>> rG;
    vector<int> vs;
    vector<bool> used;
    vector<int> cmp;
public:
    SCC(int _n) : n(_n), G(_n), rG(_n), used(_n), cmp(_n) {}
    void addEdge(int from, int to) {
        G[from].emplace_back(to);
        rG[to].emplace_back(from);
    }
    void dfs(int v) {
        used[v] = true;
        for (auto nxt : G[v]) if (!used[nxt]) dfs(nxt);
        vs.emplace_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto nxt : rG[v]) if (!used[nxt]) rdfs(nxt, k);
        vs.emplace_back(v);
    }
    int scc() {
        used.assign(n, false);
        rep(v, n) if (!used[v]) dfs(v);
        used.assign(n, false);
        int k = 0;
        for (int i = (int)vs.size() - 1; i >= 0; i--) {
            int v = vs[i];
            if (!used[v]) rdfs(v, k++);
        }
        return k;
    }
    bool same(int a, int b) {
        return cmp[a] == cmp[b];
    }
};

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

    int n, m;
    cin >> n >> m;
    SCC scc(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        scc.addEdge(a, b);
    }

    scc.scc();

    int q;
    cin >> q;
    rep(i, q) {
        int a, b;
        cin >> a >> b;
        cout << scc.same(a, b) << endl;
    }
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main() {
  string s;
  vector<string>S;
  int K;
  cin >> s >> K;
  int tmp = min(5,(int)s.size());
  for(int i = 1; i <= tmp; i++){
      for(int j = 0; j < s.size(); j++){
          S.push_back(s.substr(j,i));
      }
  }
  sort(S.begin(),S.end());
  S.erase(unique(S.begin(), S.end()), S.end());

  cout << S[K-1] << endl;

  return 0;
}

Measured memory_bytes: 1660
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

string s, t;
int ans = 10000;

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> s >> t;
	for (int i = 0; i <= (int)s.size() - (int)t.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < (int)t.size(); j++)if (s[i + j] != t[j])cnt++;
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3632
package main

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

func main() {
	n := getInt()
	ds := getIntSlice(n)

	sort.Ints(ds)

	fmt.Println(ds[n/2] - ds[n/2-1])
}

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

var scanner = wordScanner()

func wordScanner() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}

func getInt() int {
	scanner.Scan()
	i, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	scanner.Scan()
	s := scanner.Text()
	return s
}


Measured memory_bytes: 2048
#pragma comment(linker, "/STACK:10240000")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

int a[MAXN], b[MAXN];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    int maxn = 0, count = 0;
    b[n] = a[n];
    for (int i = n - 1; i >= 1; i --)
    {
        b[i] = a[i];
        if (b[i + 1] > b[i])
        {
            b[i] = b[i + 1];
        }
        int tmp = b[i] - a[i];
        if (tmp > maxn)
        {
            maxn = tmp;
            count = 1;
        }
        else if (tmp == maxn)
        {
            count ++;
        }
    }
    printf("%d\n", count);
    return 0;
}


Measured memory_bytes: 1024
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    h = [I() for _ in range(N)]
    h.sort()

    ans = INF
    for i in range(N - K + 1):
        ans = min(h[i+K-1] - h[i], ans)

    print(ans)

if __name__ == '__main__':
    resolve()


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

using namespace std;

const int N = 1e5 + 5, mod = 998244353;

int cnt[N], d[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", d+i);
    ++cnt[d[i]];
  }
  for (int i = 1; i < n; ++i) {
    if (d[i] == 0) {
      puts("0");
      return 0;
    }
  }
  if (d[0] != 0) {
    puts("0");
    return 0;
  }
  long long ans = 1;
  for (int i = 1; i < n; ++i) {
    int c = cnt[d[i]-1];
    ans = (ans * c) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}


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

typedef long long ll;

using namespace std;

bool isPalindrome(string s) {
	return (s == string(s.rbegin(), s.rend()));
}
int main() {
	string s; cin >> s;
	if(isPalindrome(s) and isPalindrome(s.substr(0, (s.length()-1)/2)) and isPalindrome(string(s.begin() + (s.length() + 3)/2 -1, s.end()))) {cout << "Yes";}
	else cout << "No";
}






Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
A = sorted((int(x) for x in input().split()))

parent = [A[-1]]
rest = A[:-1]
bl = True
for _ in range(N):
    next_parent = []
    next_rest = []
    for p in parent[::-1]:
        while rest:
            x = rest.pop()
            if x < p:
                next_parent.append(x)
                break
            else:
                next_rest.append(x)
                continue
    parent += next_parent
    parent.sort()
    rest = rest + next_rest[::-1]

bl = len(parent) == (2**N)
answer = 'Yes' if bl else 'No'
print(answer)



Measured memory_bytes: 119356
import bisect

n = int(input())
robots = []
for _ in range(n):
	x, l = list(map(int, input().split()))
	right_x = x + l
	robots.append([right_x, x, l])

robots.sort()
right_x_list = [x[0] for x in robots]
# 最も右翼がiのときの最大の残せる個数
dp = [0 for _  in range(n + 1)]

for i in range(0, n):
	j = bisect.bisect_right(right_x_list, robots[i][1] - robots[i][2])
	#print(i, j)
	dp[i + 1] = max(dp[j] + 1, dp[i])

print(dp[-1])

Measured memory_bytes: 27528
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cassert>

//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;

//std::cout << std::fixed << std::setprecision(10)
//std::ios::sync_with_stdio(false);
//constexpr long long MOD = 1000000007;

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

int main()
{
  int A[3][3] = {};
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j)
      std::cin >> A[i][j];
  int N;
  std::cin >> N;
  auto check = [&A]() {
    bool ans = false;
    for(int i = 0; i < 3; ++i)
    {
      ans |= (std::count(A[i], A[i]+3, 0) == 3);
    }
    for(int i = 0; i < 3; ++i)
    {
      bool tmp = true;
      for(int j = 0; j < 3; ++j)
      {
        tmp &= (A[j][i]==0);
      }
      ans |= tmp;
    }
    bool tmp = true;
    for(int i = 0; i < 3; ++i)
    {
      tmp &= (A[i][i]==0);
    }
    ans |= tmp;
    tmp=true;
    for(int i=0;i<3;++i)
    {
      tmp&=(A[i][3-i-1]==0);
    }
    ans |= tmp;
    return ans;
  };
  while(N--)
  {
    int b;
    std::cin >> b;
    for(auto& vec: A)
      for(auto& val: vec)
        val = (val==b?0:val);
  }
  std::cout << (check()?"Yes":"No") << std::endl;
  return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>

#define REP(i,n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define ALLOF(c) c.begin(), c.end()
#define RANGEOF(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define EPS 1e-9
#define INF 1000000000
using namespace std;

typedef complex<int> POINT;
template <class T>
class vevector : public vector<vector<T>>
{
public:
	using vector<vector<T>>::operator []; 
	T& operator [](const POINT &index) { return (*this)[index.real()][index.imag()]; }
};

template <class T> T read() { T t; cin >> t; return t; }
template <> POINT read<POINT>() { int x, y; cin >> x >> y; return POINT(x, y); }
template <class T> vector<T> read(int n) { vector<T> v; REP(i,n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i,n) v.push_back(read<T>(m)); return v; }
template <class T> void write(const T &t) { cout << t << endl; }
template <class T> void write(const T &t, const T &t2) { cout << t << ' ' << t2 << endl; }

template <class T> void write(const vector<T> &v)
{
	ostringstream ss; 
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	cout << s.substr(0, s.length() - 1) << endl;
}

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__

void solve();
int main() { solve(); return 0; }

vector<unsigned char> isPrime;
vector<int> primes;
void initPrimes(int n)
{
	isPrime = vector<unsigned char>(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	FOR(i, 2, n)
	{
		if (!isPrime[i]) continue;
		primes.push_back(i);
		for (int j = i * 2; j <= n; j += i)
			isPrime[j] = false;
	}
}
/// template end ///

void solve()
{
	READ(int, datasets);
	REP(dataset, datasets)
	{
		READ(string, s);
		set<string> st;
		FOR(i,1,s.length())
		{
			string pre = s.substr(0, i);
			string suf = s.substr(i, string::npos);
			string rsuf, rpre;
			reverse_copy(ALLOF(pre), back_inserter(rpre));
			reverse_copy(ALLOF(suf), back_inserter(rsuf));

			st.insert(pre  + suf);
			st.insert(pre  + rsuf);
			st.insert(rpre + suf);
			st.insert(rpre + rsuf);
			st.insert(suf  + pre);
			st.insert(suf  + rpre);
			st.insert(rsuf + pre);
			st.insert(rsuf + rpre);
		}
		write(st.size());
	}
}

Measured memory_bytes: 1300
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    int n;
    cin >> n;
    map<int, int> even, odd;
    rep(i, n) {
        int v; cin >> v;
        if(i % 2 == 0) even[v]++;
        else odd[v]++;
    }
    even[0]; odd[0];
    vector<P> vec_even, vec_odd;
    for(auto x : even) {
        vec_even.push_back(P(x.first, x.second));
    }
    for(auto x : odd) {
        vec_odd.push_back(P(x.first, x.second));
    }
    sort(ALL(vec_even), [](P a, P b) {
        return a.second > b.second;
    });
    sort(ALL(vec_odd), [](P a, P b) {
        return a.second > b.second;
    });
    int ans = n - vec_even[0].second - vec_odd[0].second;
    if(vec_even[0].first == vec_odd[0].first) {
        ans = min(n - vec_even[0].second - vec_odd[1].second, n - vec_even[1].second - vec_odd[0].second);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6136
#include <bits/stdc++.h>
using namespace std;
#define min(a, b) ((a<b)?a:b)
#define max(a, b) ((a<b)?b:a)
#define pb push_back
#define endl "\n"
typedef long long ll;

#define max_element mmmmm
#define min_element nnnnn

template<class T>
class BIT {
	public:
		int BIT_size;
		vector<T> BIT_array;
		BIT(int BIT_size) {
			this->BIT_size = BIT_size;
			BIT_array = vector<T>(BIT_size+1);
			fill(BIT_array.begin(), BIT_array.end(), 0);
		}
		void BIT_update(int i, T d) {
			for(; i<=BIT_size; i+=(i&-i)) {
				BIT_array[i] += d;
			}
		}
		T BIT_sum(int i) {
			T BIT_sum_result = 0;
			for(; i>0; i-=(i&-i)) {
				BIT_sum_result += BIT_array[i];
			}
			return BIT_sum_result;
		}				
};

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

 
int main() {
	double r; cin >> r;
	cout << r*3.141592*2 << endl;
}







































































Measured memory_bytes: 3792
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}
int main() {
  int N; cin >> N;
  vector<int> a(N); cin >> a;
  int vmax = 0, vmin = 0, i1, i2;
  for (int i = 0; i < N; ++i) {
    if (vmax < a[i]) {
      vmax = a[i];
      i1 = i;
    }
    if (vmin > a[i]) {
      vmin = a[i];
      i2 = i;
    }
  }

  if (vmin < 0 && 0 < vmax) {
    cout << 2 * N - 1 << endl;
    if (abs(vmin) < vmax) {
      vmin += vmax;
      for (int i = 0; i < N; ++i) {
        cout << i1 + 1 << " " << i + 1 << endl;
      }
    } else {
      vmax += vmin;
      for (int i = 0; i < N; ++i) {
        cout << i2 + 1 << " " << i + 1 << endl;
      }
    }
  } else {
    cout << N - 1  << endl;
  }

  if (vmin >= 0) {
    for (int i = 0; i < N-1; ++i) {
      cout << i + 1 << " " << i + 2 << endl;
    }
  } else if (vmax <= 0) {
    for (int i = N-1; i > 0; --i) {
      cout << i + 1 << " " << i << endl;
    }
  } else {
    assert(false);
  }
}


Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        c: [Chars; h],
    }

    let mut ans = 0;
    for bit1 in 0 .. (1_usize << h) {
        for bit2 in 0 .. (1_usize << w) {
            let mut sum = 0;
            for i in 0 .. h {
                if ((bit1 >> i) & 1) == 1 { continue };
                for j in 0 .. w {
                    if ((bit2 >> j) & 1) == 1 { continue };
                    if c[i][j] == '#' { sum += 1 };
                }
            }
            if sum == k { ans += 1 };
        }
    }

    println!("{}", ans);

}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename key> using ordered_set = tree <key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main () {
   IO;
   long long int a, b;
   cin >> a >> b;
   long long g = __gcd(a, b);
   cout << a * b / g;
   return 0;
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    ll A, V, B, W, T; cin >> A >> V >> B >> W >> T;

    if(V < W) {
        puts("NO");
        return 0;
    }
    
    if(A > B) A *= -1, B *= -1;
    ll diff_pos = B - A;
    ll diff_velo = V - W;
    if(diff_pos <= T * diff_velo) puts("YES");
    else puts("NO");
    return 0;
}


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

vector<int> v[111111];
long s[2222], t[2222], d[2222][2222], e[2222][2222], z[2222];
int main() {
	int n, m, p = 1e9 + 7;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> s[i], v[s[i]].push_back(i);
	for (int i = 0; i < m; i++)
		cin >> t[i];
	for (int j = 0; j < m; j++) {
		for (int i = 1; i <= n; i++) {
			d[i][j + 1] = d[i][j];
			if (!z[j]) {
				z[j] = 1;
				int k = 0;
				for (int x : v[t[j]]) {
					for (; k < x; k++) e[k + 1][j] = e[k][j];
					(e[x][j] += d[x][j] + 1) %= p;
				}
				for (; k < 2200; k++) e[k + 1][j] = e[k][j];
			}
			(d[i][j + 1] += e[i - 1][j]) %= p;
		}
	}
	cout << (d[n][m] + 1) % p << endl;
	return 0;
}


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

int main(){

	int r, c;
	cin >> r >> c;
	int value[r+1][c+1];

	//初期化
	for(int i=0; i<r+1; i++){
		for(int j=0; j<c+1; j++){
			value[i][j] =0;
		}
	}

	//入力
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			cin >> value[i][j] ;
		}
	}

	//合計　行末
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			value[i][c] += value[i][j];
		}
	}

	//合計　列末
	for(int i=0; i<c+1; i++){
		for(int j=0; j<r; j++){
			value[r][i] += value[j][i];
		}
	}

	//表示
	for(int i=0; i<r+1; i++){
		for(int j=0; j<c+1; j++){
			if(j) cout << " ";
			cout << value[i][j];
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3096
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
######################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
H, W = LI()
c = [LI() for _ in range(10)]
A = [LI() for _ in range(H)]
d = [[float("inf") for i in range(10)] for i in range(10)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    for j in range(10):
        d[i][j] = c[i][j]
for i in range(10):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(10,d))
L = warshall_floyd(10,d)
cur = int(0)
for i in range(H):
    for j in range(W):
        l = A[i][j]
        if l>=0:
            cur += L[l][1]

ans = cur
print(ans)


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

namespace AOJ0061
{
    class Program
    {
        static void Main(string[] args)
        {
            var data = ReadData().OrderByDescending(tiegroup => tiegroup.Key);

            foreach (var id in ReadInquiries())
            {
                var index = 1;
                foreach (var tiegroup in data)
                {
                    if (tiegroup.Select(values => values[0]).Contains(id))
                    {
                        Console.WriteLine(index);
                        break;
                    }

                    index++;
                }
            }
        }

        public static ILookup<int, int[]> ReadData()
        {
            var list = new List<int[]>();

            string line;
            while ((line = Console.ReadLine()) != null && line != "0,0")
            {
                list.Add(line.Split(',').Select(int.Parse).ToArray());
            }

            return list.ToLookup(values => values[1]);
        }

        public static IEnumerable<int> ReadInquiries()
        {
            string line;
            while ((line = Console.ReadLine()) != null)
            {
                yield return int.Parse(line);
            }
        }
    }
}

Measured memory_bytes: 6844
N = int(input())
A = list(map(int, input().split()))

# NOTE: 間に合わない
# for i in range(N):
#     ans = 0
#     now = 0
#     for j, a in enumerate(A):
#         if i == j:
#             continue
#         ans += abs(now - a)
#         now = a
#     ans += abs(0 - now)
#     print(ans)

HEAD = []
TAIL = []
now = 0
tmp = 0
for ai in A + [0]:
    tmp += abs(ai - now)
    now = ai
    HEAD.append(tmp)

now = 0
tmp = 0
for ai in A[::-1] + [0]:
    tmp += abs(ai - now)
    now = ai
    TAIL.append(tmp)

# print(HEAD)
# print(TAIL)

ans = 0
for i in range(N):
    if i == 0:
        ans = abs(A[1] - 0) + TAIL[N-2]
    elif i == N - 1:
        ans = abs(A[N-2] - 0) + HEAD[N-2]
    else:
        # print(HEAD[i-1], TAIL[N-i-2], abs(A[i+1] - A[i-1]), i, N-i-2)
        ans = HEAD[i-1] + TAIL[N-i-2] + abs(A[i+1] - A[i-1])
    print(ans)

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

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 100010
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void solve(void)
{
  int n,k; cin>>n; cin>>k;
  int l = 0, r = 1e9 + 1;
  vector<int> vec (n,0);
  for (int i = 0; i < n; i++)
  {
     cin>>vec[i];
  }
  while(r - l > 1)
  {
    int mid = (l + r)/2;
    //mid以下になるように切るには何回必要か？
    int cnt  = 0;
    for (int i = 0; i < n; i++)
    {
      cnt += vec[i]/mid - (vec[i]%mid == 0);
    }
    if(cnt <= k)r = mid;
    else l = mid;
    // DEBUG(cnt,l,r,"\n");
  }
  cout<<(int)ceil(l) + 1<<endl;
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


Measured memory_bytes: 4712
function Main(input) {
  var inputs = input.split('\n')
  var branch_number = inputs[0]
  var branches = inputs[1].split(' ')
  var result = 0

  var sum = parseInt(branches[0])
  var branch_sum = []
  branch_sum[0] = parseInt(branches[0])
  for (i = 1; i < branch_number; i++) {
    sum += parseInt(branches[i])
    branch_sum[i] = branch_sum[i-1] + parseInt(branches[i])
  }

  var half = sum / 2

  var j = 0
  var flag = false
  var index = 0
  while (!flag) {
    if (Math.abs(branch_sum[j] - half) <= Math.abs(branch_sum[j+1] - half)) {
      index = j
      flag = true
    }
    j++
  }
  // 割れたら終わり
  if (branch_sum[index] === half) {
    console.log(result)
    return
  }

  var center = branch_sum[index]

  var plus = false
  if (center < half) {
    plus = true
  }
  var diff = 0
  while (center !== half) {
    if (plus) {
      diff = Math.ceil(half - center)
      result += diff
      center += diff
      sum += diff
      half = sum / 2
    } else {
      diff = Math.ceil(center - half)
      result += diff
      center -= diff
      sum -= diff
      half = sum / 2
    }
  }

  console.log(result)

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

typedef long long int ll;

int main()
{
    ll n;
    cin >> n;
    bool f = false;
    for(ll i = 1;i < 10;i++){
        ll t = 0;
        if(n % i == 0){
            t = n / i;
        }
        if(t > 0 && t < 10){
            f = true;
        }
    }

    if(f){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
    return 0;
}

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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }
    vector<vector<int>> A(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        ll sum = 0;
        for (int j = 0; j < M; j++) {
            sum += A[i][j] * B[j];
        }
        if (sum + C > 0) {
            ans++;
        }
    }

    cout << ans << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

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

int n,k,mod,fff[161][161],m,ans1,ans2,f[81][81][81],mi[81],Sum[81][81],s[81][81],nwS[81],nws[81];

int add(int x,int y) {return (x+y>=mod?x+y-mod:x+y);}

int main()
{
	scanf("%d%d%d",&n,&k,&mod);
	if (!(k&1))
	{
		fff[0][0]=1,k>>=1,m=(n+1>>1),k++;
		for (int i=0; i<m; i++)
			for (int j=0; j<k; j++) if (fff[i][j])
			{
				fff[i+1][j+1]=(fff[i+1][j+1]+fff[i][j])%mod;
				fff[i+1][0]=(fff[i+1][0]+fff[i][j])%mod;
			}
		ans1=ans2=0;
		for (int i=0; i<k; i++) ans1=(ans1+fff[n>>1][i])%mod;
		for (int i=0; i<k; i++) ans2=(ans2+fff[n+1>>1][i])%mod;
		return printf("%d\n",1ll*ans1*ans2%mod),0;
	} 
	mi[0]=1;
	for (int i=1; i<=80; i++) mi[i]=2ll*mi[i-1]%mod;
	m=(n>>1),n=(n+1>>1);
	for (int k=0; k<=m; k++) Sum[0][k]=mi[k];
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=i; j++)
		{
			int l=max(j-2,0);
			if (i-j+1>=k+1) f[i][i-(k+1>>1)+1][i-(k+1>>1)]=add(f[i][i-(k+1>>1)+1][i-(k+1>>1)],Sum[l][j+(k>>1)-1]);
			else
			{
				for (int o=(j+(k>>1)>m)?1:max(1,i-(k+1>>1)+1); o<=j+(k>>1)+1&&o<=m+1; o++)
					f[i][o][min(j+(k>>1),m)]=add(f[i][o][min(j+(k>>1),m)],Sum[l][max(o-2,0)]),
					f[i][o][min(j+(k>>1),m)]=add(f[i][o][min(j+(k>>1),m)],s[l][o]);
			}
		}
		nwS[0]=0;
		for (int j=0; j<=m+1; j++) nwS[0]=add(nwS[0],f[i][j][0]);
		for (int j=1; j<=m; j++)
		{
			nwS[j]=0;
			for (int k=0; k<=m+1; k++) nwS[j]=add(nwS[j],f[i][k][j]);
			nwS[j]=add(add(nwS[j-1],nwS[j-1]),nwS[j]);
		}
		for (int j=0; j<=m; j++) Sum[i][j]=add(Sum[i-1][j],nwS[j]);
		for (int j=1; j<=m+1; j++)
		{
			nws[j]=0;
			for (int k=0; k<=m; k++) nws[j]=add(nws[j],f[i][j][k]);
		}
		for (int j=1; j<=m+1; j++) s[i][j]=add(s[i-1][j],nws[j]);
	}
	return printf("%d\n",Sum[n][m]),0;
}

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

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

int main(){
    string S, T;
    cin >> S >> T;
    string S_fix = S;
    bool is_can = false;
    int length = (int)S.size();
    for(int i = 0; i < length ; i++){
        for(int j = 0; j < length; j++){
            S_fix[j] = S[(i + j) % length];
        }
        if(S_fix == T){
            is_can = true;
            break;
        }
    } 
    if(is_can) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
using namespace std;
typedef long long ll;

int modulo = 1000000007; // 10^9 + 7

// 階乗
ll factorial(int N) {
	if (N == 0) return 1;
	ll temp = N * factorial(N - 1);
	if (temp >= modulo) return temp % modulo;
	else return  temp;
}

int main() {
	int N, M; cin >> N >> M;

	if (abs(N - M) > 1) cout << 0 << endl;
	else {
		ll combi;
		combi = (factorial(N) * factorial(M)) % modulo;
		if (N != M) cout << combi << endl;
		else cout << (combi * 2) % modulo;
	}

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int main() {
  int r,c,k;
  cin>>r>>c>>k;
  ll memo[r+1][c+1];
  for(int i=0;i<r+1;i++){
    for(int j=0;j<c+1;j++){
      memo[i][j]=0;
    }
  }
  for(int i=0;i<k;i++){
    int R,C;
    ll v;
    cin>>R>>C>>v;
    memo[R][C]=v;
  }
  vector<vector<vector<ll>>> dp(r+1,vector<vector<ll>>(c+1,vector<ll>(4,0)));
  for(int i=0;i<r+1;i++){
    for(int j=0;j<c+1;j++){
      for(int l=0;l<4;l++){
        dp[i][j][l]=0;
      }
    }
  }
  for(int i=1;i<r+1;i++){
    for(int j=1;j<c+1;j++){
      for(int l=0;l<4;l++){
        dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][l]);
      }
      dp[i][j][0]=max(dp[i][j][0],dp[i][j-1][0]);
      dp[i][j][1]=max(dp[i][j-1][1],dp[i][j][0]+memo[i][j]);
      dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+memo[i][j]);
      dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+memo[i][j]);
    }
  }
  ll ans=0;
  for(int i=0;i<4;i++){
    ans=max(ans,dp[r][c][i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 706856
#include <stdio.h>
 
int main()
{
 
   int n;
  int i;
  int flag=0;
  scanf("%d",&n);
  for(i=1;i<=9;++i)
  {
      if(n%i==0)
      {
        if((n/i)<=9)
        {
          flag=1;
          break;
        }
      }
  }
  
  if(flag==1)
      printf("Yes");
  
  else
      printf("No");
   
  
  
}

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

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main() {
  int a, b, c, d;
  scanf("%d %d %d %d", &a, &b, &c, &d);

  if ((a+b) > (c+d)) printf("Left\n");
  else if ((a+b) < (c+d))printf("Right\n");
  else if ((a+b) == (c+d))printf("Balanced\n");
  return 0;
}

Measured memory_bytes: 128
var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
var abs = x=>x>0?x:-x;
function min(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<val)val = rest[i];return val}
function max(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>val)val = rest[i];return val}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
 
function Main(input){
	var input = input.split('\n');
	var nk = toIntArr(input[0].split(' '));
	var n = nk[0];
	var k = nk[1];
	var xs = toIntArr(input[1].split(' '));

	var s = n-k;
	var ans = Infinity;
	var L,R;
	var temp;
	for(var i = 0; i <= s; i++){
		L = xs[i];
		R = xs[i+k-1];
		if(R<0){
			temp = -L;
		}else if(L>0){
			temp = R;
		}else{
			temp = min(2*R-L,R-2*L);
		}
		ans = min(ans,temp);
	}
	console.log(ans);
}

Measured memory_bytes: 28680
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=3.14159265358979323846;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n,m,l;
    cin>>n>>m>>l;
    vector<vector<ll>> d(n,vector<ll>(n,LINF));
    rep(i,m) {
        int a,b; ll c;
        cin>>a>>b>>c;
        a--;b--;
        if(c>l) continue;
        d[a][b]=c;
        d[b][a]=c;
    }
    
    rep(k,n) rep(i,n) rep(j,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    
    vector<vector<ll>> e(n,vector<ll>(n,LINF));
    rep(i,n) {
        rep(j,n) {
            if(d[i][j]<=l) e[i][j]=1;
        }
    }
    
    rep(k,n) rep(i,n) rep(j,n) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
    
    int q;
    cin>>q;
    vector<ll> ans(q);
    rep(i,q) {
        int s,t;
        cin>>s>>t;
        s--;t--;
        ans[i]=(e[s][t]==LINF ? -1 : e[s][t]-1);
    }
    
    for(ll x:ans) cout<<x<<endl;
    
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    double t, x;
    cin >> t >> x;
    cout << fixed << setprecision(12) << t/x << endl;
    return 0;
}




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

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var fare = new int[4];
            for (int i = 0; i < fare.Length; i++)
                fare[i] = int.Parse(Console.ReadLine());

            Console.WriteLine(Math.Min(fare[0], fare[1]) + Math.Min(fare[2], fare[3]));
        }
    }
}


Measured memory_bytes: 11092
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int main(){

  int n;  cin >>n;
  set<string>st;
  string b4;

  for(int i = 0; i < n; i++){
    string  str;  cin >> str;
    if(st.count(str)){
      cout << "No\n";
      return 0;
    }
    st.insert(str);
    if(i && str[0] != b4.back()){
      cout << "No\n";
      return 0;
    }
    b4 = str;
  }

  cout << "Yes\n";

  return 0;
}


Measured memory_bytes: 256
n = int(input())
if n % 10 == 1:
    m = 9
else:
    m = 1
if (n // 10) % 10 == 1:
    m += 90
else:
    m += 10
if (n // 100) % 10 == 1:
    m += 900
else:
    m += 100
print(m)
  

Measured memory_bytes: 2940
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int x[] = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        int y[] = x.clone();
        Arrays.sort(y);
        int m1 = y[n / 2 - 1];
        int m2 = y[n / 2];
        PrintWriter pw = new PrintWriter(System.out);
        if (m1 == m2) {
            for (int i = 0; i < n; i++) {
                pw.println(m1);
            }
            pw.flush();
            return;
        }
        for (int i = 0; i < n; i++) {
            if (x[i] <= m1) {
                pw.println(m2);
            } else {
                pw.println(m1);
            }
        }
        pw.flush();
    }
}

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

using namespace std;
typedef long long ll;
const int MAXN = 1e4 + 10, N = 2000 + 5, M = 4500 + 5;
const ll MOD = 1e9 + 7;
int n;
ll cnt1[M][M], cnt2[M][M], dp[M][M];
ll fac[MAXN], inv[MAXN];
ll menha, ans;

ll pw(ll a, ll b){
	if( b == 0) return 1LL;
	if( b % 2) return (pw(a*a%MOD, b/2LL) * a) % MOD;
	else return pw(a*a%MOD, b/2LL) % MOD;
}

ll c(ll k, ll n){
	ll ans = (fac[n] * inv[k]) % MOD;
	ans = (ans * inv[n - k]) % MOD;
	return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
	fac[0] = 1, inv[0] = 1;
	for(int i = 1; i < MAXN; i ++)
		fac[i] = (1LL * fac[i - 1]*i)%MOD, inv[i] = pw(fac[i], MOD - 2LL);
	for( int i = 0; i < n;i ++){
		int a, b;
		cin >> a >> b;
		cnt1[a + N][b + N] ++;
		cnt2[N - a][N - b] ++;
		dp[N - a][N - b] ++;
		menha = (menha + c(2LL*a, 2LL*a + 2LL*b)) % MOD;
	}
	ans = MOD + -menha;
	for(int i = 1; i < M; i ++){
		for(int j = 1; j < M; j ++){
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
			dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
			if( cnt1[i][j] ) ans = (ans + dp[i][j]*cnt1[i][j]%MOD) % MOD;
		}
	}
	ans = (ans * pw(2, MOD - 2)) % MOD;
	cout << ans % MOD << endl;
    return 0;
}


Measured memory_bytes: 239536
n = int(input())
t , a = map(int , input().split())
h = list(map(int , input().split()))
ans = 100000
place = 0
for i in range(1 , n + 1):
  celsius = t - 0.006 * h[i - 1]
  if abs(ans - a) > abs(celsius - a):
    place = i
    ans = celsius

print(place)

Measured memory_bytes: 3064