akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    ll ans = 0;
    rep(i, n) ans += s[i] - '0';

    if (ans % 9 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll c,a[N],b[N],pre[N],bk[N],pp[N],bb[N];
ll dis(ll x,ll y)
{
    return min(abs(x-y),c-abs(x-y));
}
ll solve()
{
    ll ans=0,pos=0,res=0;
    int l=1,r=n;
    while(l<=r)
    {
        if(b[l]-dis(pos,a[l])>b[r]-dis(pos,a[r]))
        {
            res+=b[l]-dis(pos,a[l]);
            ans=max(ans,res);
            pos=a[l++];
        }
        else
        {
            res+=b[r]-dis(pos,a[r]);
            ans=max(ans,res);
            pos=a[r--];
        }
    }
    return ans;
}
ll solve2()
{
    ll ans=0,pos=0,res=0;
    int l=1,r=n;
    while(l<=r)
    {
        if(dis(pos,a[l])<b[r]-dis(pos,a[r]))
        {
            res+=b[l]-dis(pos,a[l]);
            ans=max(ans,res);
            pos=a[l++];
        }
        else
        {
            res+=b[r]-dis(pos,a[r]);
            ans=max(ans,res);
            pos=a[r--];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%lld",&n,&c);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1]+b[i]-(a[i]-a[i-1]),ans=max(ans,pre[i]);
    }
    a[n+1]=c;
    for(int i=n;i>=1;i--)
        bk[i]=bk[i+1]+b[i]-(a[i+1]-a[i]),ans=max(ans,bk[i]);
    for(int i=n;i>=1;i--)
        bb[i]=max(bk[i],bb[i+1]);
    for(int i=1;i<=n;i++)
        pp[i]=max(pre[i],pp[i-1]);
    for(int i=n;i>=1;i--)
        ans=max(ans,bk[i]-(c-a[i])+pp[i-1]);
    for(int i=1;i<=n;i++)
        ans=max(ans,pre[i]-a[i]+bb[i+1]);
    ans=max(ans,solve());
    ans=max(ans,solve2());
    printf("%lld\n",ans);
}


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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long

const int mod = 1000000007;

int32_t main() {

    int n, m; cin >> n >> m;
    vector<bool> bad(n+1, false);
    for(int i = 0; i < m; ++i) {
        int a; cin >> a;
        bad[a] = true;
    }
    
    vector<int> dp(n+1, 0);
    dp[0] = 1;

    for(int i = 1; i <= n; ++i) {
        if(!bad[i]) {
            dp[i] += dp[i-1];
            if(i > 1) dp[i] += dp[i-2];
            dp[i] %= mod;
        }
    }

    cout << dp[n] << endl;
    
    return 0;
}


Measured memory_bytes: 1024
import sys
string = input()

ch_1 = ""
ch_2 = ""
ct_1 = 0
ct_2 = 0
for ch in string:
  
  if ch_1 != ch and ch_2 != ch and ch_1 is not "" and ch_2 is not "":
    print("No")
    sys.exit(0)
  if ch_1 != ch:
    if ch_1 == "":
      ch_1 = ch
    else:
      ch_2 = ch

  if ch_1 == ch:
    ct_1 += 1
  elif ch_2 == ch:
    ct_2 += 1


if ct_1 == 2 and ct_2 == 2:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(void){
  string s, ans;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
  if(i % 2 == 0){
      ans += s.at(i);
  }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
# 解説AC
N = int(input())
A = [int(i) for i in input().split()]

MAXA = max(A)
MINA = min(A)

if MAXA - MINA >= 2:
    flag = False
elif MAXA - MINA == 0:
    # 全てalone -> 種類数はN
    flag = True if (A[0] == N - 1) else False
    # 全てaloneではない -> 種類数はN/2以下
    flag |= True if (2 * A[0] <= N) else False
else:
    x = A.count(MINA) # alonaな猫の匹数
    y = A.count(MAXA) # aloneではない猫の匹数
    # MAXA - x: aloneではない猫の種類数
    flag = True if (x < MAXA and 2 * (MAXA - x) <= y) else False

if flag:
    print('Yes')
else:
    print('No')

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

static const int INF = 1e9;

int d[4][4];

int main(){

    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            d[i][j] = INF;
        }
    }
    
    for(int i=0; i<3; i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        d[a][b] = 1;
        d[b][a] = 1;
    }

    for(int k=0; k<4; k++){
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }

    bool flag = false;

    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            if(d[i][j] == 3){
                flag = true;
            }
        }
    }

    cout<<(flag ? "YES" : "NO")<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll k,n,a[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll ans=0;
	for(int i=2;i<=n;i++){
		ans=max(min(abs(a[i]-a[i-1]),k-abs(a[i]-a[i-1])), ans);
	}
	ans=max(min(abs(a[n]-a[1]),k-abs(a[n]-a[1])), ans);
	cout<<k-ans<<'\n';
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define MAX 2100000
#define INF 1001000000
using Graph=vector<vector<int>>;

int main(){
  int N;
  cin>>N;
  vector<int> L(2*N);
  for(int i=0;i<2*N;i++){
    cin>>L.at(i);
  }
  sort(L.begin(),L.end());

  int ans=0;
  for(int i=0;i<N;i++){
    ans+=min(L.at(2*i),L.at(2*i+1));
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 60);
const bool WHITE = false;
const bool BLACK = true;

int main()
{
  int N, M, r;
  cin >> N >> M >> r;
  vector<vector<pair<int, int>>> adj(N);
  for (int i = 0; i < M; i++)
  {
    int s, t, d;
    cin >> s >> t >> d;
    adj.at(s).push_back(make_pair(t, d));
  }
  vector<long long> d(N, INF);
  vector<bool> color(N, WHITE);
  priority_queue<pair<long long, int>> pq;
  pq.push(make_pair(0, r));
  while (!pq.empty())
  {
    long long cost;
    int u;
    tie(cost, u) = pq.top();
    cost *= -1;
    pq.pop();
    if (color.at(u) == BLACK)
    {
      continue;
    }
    color.at(u) = BLACK;
    d.at(u) = cost;
    for (int i = 0; i < adj.at(u).size(); i++)
    {
      int v, cost_uv;
      tie(v, cost_uv) = adj.at(u).at(i);
      if (color.at(v) == WHITE && d.at(v) > d.at(u) + cost_uv)
      {
        pq.push(make_pair(-1 * (d.at(u) + cost_uv), v));
      }
    }
  }
  for (int i = 0; i < N; i++)
  {
    if (d.at(i) < INF)
    {
      cout << d.at(i) << endl;
    }
    else
    {
      cout << "INF" << endl;
    }
  }
}


Measured memory_bytes: 16544
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define mod 1000000007
typedef long long int ll;
int u(const void *a, const void *b){
    return *(ll*)a-*(ll*)b;
}
int d(const void *a, const void *b){
    return *(ll*)b-*(ll*)a;
}
int min(int a,int b){
  if(a>b)return b;
  return a;
}
int max(int a,int b){
  if(a>b)return a;
  return b;
}
int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}
int kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
char s[100001];
int main(void){
  char c[4][8]={"maerd","remaerd","esare","resare"};
  int l[4]={5,7,5,6};
  scanf("%s",s);
  int n=strlen(s);
  FOR(n/2){
    int t=s[i];
    s[i]=s[n-i-1];
    s[n-i-1]=t;
  }
  int x=0;
  while(x<n){
    int y=x;
    FOR(4){
      int f=1;
      FORJ(l[i])if(s[x+j]!=c[i][j])f=0;
      if(f)x+=l[i];
    }
    if(x==y){
      PRS("NO");
      return 0;
    }
  }
  PRS("YES");
  return 0;
}


Measured memory_bytes: 256
while True:
    (H, W) = [int(i) for i in input().split()]
    if  (H == 0 == W):
        break
    for hc in range(H):
        for wc in range(W):
            if(hc + wc) %  2 == 0:
                print('#', end='')
            else:
                print('.', end='')
        print()
    print()

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

using namespace std;

const int N=1e6+3;

const double eps=0.000000001;

#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;

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

const int inf=1e9;

int n,m,a[N],b[N],k,q,u,v,x,y,tc,c,l,r,ans;

char s[N];

void IO(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("test.txt","r",stdin);
	#endif
}

int main(){
	//IO();
	scanf("%d%d",&n,&m);
	if (n==m)
		printf("Yes\n");
	else
		printf("No\n");

}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}
	
	private void run() {
		Scanner scan = new Scanner(System.in);
		int n;
		while (true) {
			n= scan.nextInt();
			if (n == 0) break;
			int exchange = 1000 - n;
			
			int[] coin = {500, 100, 50, 10, 5, 1};
			
			int count = 0;
			for (int i = 0; i < 6; i++) {
				int num = (int)Math.floor((double)exchange / coin[i]);
				exchange %= coin[i];
				count += num;
			}
			
			System.out.println(count);
		}
		
	}

}

Measured memory_bytes: 17176
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

int main(){
    string S;
    cin>>S;
    int size=S.size();
    vector<int> N(size);
    vector<int> rN(size);
    N[0]=(int)S[size-1]-'0';
    rN[0]=10-N[0];
    for(int i=1;i<size;i++){
        N[i]=(int)S[size-i-1]-'0';
        rN[i]=9-N[i];
    }

    vector<ll> dp1(size+1);
    vector<ll> dp2(size+1);
    dp1[0]=0;dp2[0]=0;
    for(int i=1;i<size+1;i++){
        dp1[i]=min(N[i-1]+dp1[i-1],N[i-1]+1+dp2[i-1]);
        dp2[i]=min(rN[i-1]+dp2[i-1],rN[i-1]+1+dp1[i-1]);
    }
/*
    for(auto p:dp1){
        cout<<p<<" ";
    }
    cout<<endl;
    for(auto p:dp2){
        cout<<p<<" ";
    }
    cout<<endl;
    */
    cout<<min(dp1[size],dp2[size]+1)<<endl;

    return 0;
}

Measured memory_bytes: 27740
N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A = A[::-1]
B = B[::-1]
tmp = 0
ans = 0
for i in range(N):
    A[i] += ans
    add = ((A[i] - 1) // B[i] + 1) * B[i] - A[i]
    ans += add
print(ans)


Measured memory_bytes: 14900
//
// Created by seriru on 2020/06/28.
//

#include <bits/stdc++.h>
using namespace std;

constexpr int D = 365;
constexpr int NUM = 26;
int score = 0;

void print(vector<int> const& ans) {
  for (int i = 0; i < D; ++i) {
    cout << ans[i] << endl;
  }
}

int main() {
  int _;
  cin >> _;
  vector<int> C(NUM);
  vector<vector<int>> S(D, vector<int>(NUM));
  vector<int> ans(D+1);
  vector<vector<int>> last(D+1, vector<int>(NUM));

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

  for (int i = 0; i < D; ++i) {
    int maxScore = 0;
    int contest = 0;
    for (int j = 0; j < NUM; ++j) {
      cin >> S[i][j];
      if (maxScore < S[i][j]) {
        maxScore = S[i][j];
        contest = j+1;
      }
    }

    ans[i] = contest;
  }

  // greedy(ans, last, C);
  // calcBaseScore(ans, S, last, C);
  print(ans);
}


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

using namespace std;

int main()
{
   int n,k;
  int i,j,w,d;
   int array[1000];
  int sum=0;
  cin >> n >> k ;
  for(d=0; d<n; d++){
    cin >> array[d];
  }
  
  for (i = 0; i < (n - 1); i++) {
        for (j = (n - 1); j > i; j--) {
            if (array[j] < array[j - 1]) {
                w = array[j];
                array[j] = array[j - 1];
                array[j - 1] = w;
            }
        }
    }

  
  for(int i=0; i<k; i++){
    sum += array[i];
  }
  cout << sum;

   return 0;
}

Measured memory_bytes: 3164
import os
import sys

import numpy as np


def solve(inp):
    r, c, k = inp[:3]
    items = np.zeros((r + 1, c + 1), dtype=np.int64)
    rrr = inp[3::3]
    ccc = inp[4::3]
    vvv = inp[5::3]
    for r_, c_, v in zip(rrr, ccc, vvv):
        items[r_][c_] = v

    dp = np.zeros((r + 1, c + 1, 4), dtype=np.int64)

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            up = dp[i - 1][j][3]
            for w in range(4):
                dp[i][j][w] = max(dp[i][j - 1][w], up)
            v = items[i][j]
            if v == 0:
                continue
            for w in range(2, -1, -1):
                dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

    return dp[-1][-1][3]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)


Measured memory_bytes: 387160
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9+7
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;

}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int A, B;
    cin >> A >> B;
    rep(i, 1, 10001) {
        if (floor(i*0.08) == A && floor(i*0.1) == B) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
 
public class Main {
  /**
   * Main method.
   */
  public static void main(String[] args) throws IOException {
    Scanner s = new Scanner(System.in);
    
    final int A = s.nextInt();
    final int B = s.nextInt();
    final int K = s.nextInt();
    
    for (int i = A; i <= B; i++) {
    	if (i < A+K || i > B-K) {
    		System.out.println(i);
    	}
    }

  }
}


Measured memory_bytes: 21716
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node {int parent, left, right;};

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d){
    if (u == NIL) return;
    D[u] = d;
    setDepth(T[u].left, d + 1);
    setDepth(T[u].right, d + 1);
}

int setHeight(int u){
    int h1 = 0, h2 = 0;
    if (T[u].left != NIL){
        h1 = setHeight(T[u].left) + 1;
    }
    if (T[u].right != NIL){
        h2 = setHeight(T[u].right) + 1;
    }
    return H[u] = (h1 > h2 ? h1 : h2);
}

//節点uの兄弟を返す
int getSibling(int u){
    if (T[u].parent == NIL) return NIL;
    if (T[T[u].parent].left != u && T[T[u].parent].left != NIL) {
        return T[T[u].parent].left;
    }
    if (T[T[u].parent].right != u && T[T[u].parent].right != NIL){
        return T[T[u].parent].right;
    }
    return NIL;
}

void print(int u){
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", getSibling(u));
    int deg = 0;
    if (T[u].left != NIL) deg++;
    if (T[u].right != NIL) deg++;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);

    if (T[u].parent == NIL){
        printf("root\n");
    }else if (T[u].left == NIL && T[u].right == NIL){
        printf("leaf\n");
    }else {
        printf("internal node\n");
    }
}

int main(){
    int v, l, r, root = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)T[i].parent = NIL;

    for (int i = 0; i < n; i++){
        scanf("%d %d %d", &v, &l, &r);
        T[v].left = l;
        T[v].right = r;
        if (l != NIL) T[l].parent = v;
        if (r != NIL) T[r].parent = v;
    }

    for (int i = 0; i < n; i++) if (T[i].parent == NIL) root = i;

    setDepth(root, 0);
    setHeight(root);

    for (int i = 0; i < n; i++) print(i);

    return 0;

}


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

int main() {
	int n;

	cin >> n;

	int ans = 0;
	for( int i = 1; i <= n; i++ ) {
		if( (i % 2) == 0 ) {
			continue;
		}
		int num = 0;
		for( int j = 1; j <= i; j++ ) {
			if( (i % j) == 0 ) {
				num++;
			}
		}
		if( num == 8 ) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int INF=-2000000000;
int main() {
  string s;
  cin >> s;
  int n=s.size();
  while(n>0){
    if(s[n-1]=='m'&&s[n-2]=='a'&&s[n-3]=='e'&&s[n-4]=='r'&&s[n-5]=='d'){
      n-=5;
      continue;
    }
    if(s[n-1]=='r'&&s[n-2]=='e'&&s[n-3]=='m'&&s[n-4]=='a'&&s[n-5]=='e'&&s[n-6]=='r'&&s[n-7]=='d'){
      n-=7;
      continue;
    }
    if(s[n-1]=='e'&&s[n-2]=='s'&&s[n-3]=='a'&&s[n-4]=='r'&&s[n-5]=='e'){
      n-=5;
      continue;
    }
    if(s[n-1]=='r'&&s[n-2]=='e'&&s[n-3]=='s'&&s[n-4]=='a'&&s[n-5]=='r'&&s[n-6]=='e'){
      n-=6;
      continue;
    }
    break;
  }
  if(n) cout << "NO" << endl;
  else cout << "YES" << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>

template<typename T> bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

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

using namespace std;
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=1001001000;
const ll LLMAX=1010010010010010000;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll H,W;
    cin>>H>>W;
    vector<vector<bool>> obstacle(H,vector<bool>(W));
    for(int i=0;i<H;i++){
        string s;
        cin>>s;
        for(int j=0;j<W;j++){
            if(s[j]=='#')obstacle[i][j]=true;
            else obstacle[i][j]=false;
        }
    }
    vvll L(H,vll(W)),R(H,vll(W)),D(H,vll(W)),U(H,vll(W));
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(obstacle[i][j]){
                L[i][j]=-1;
                continue;
            }
            if(j==0)L[i][j]=0;
            else L[i][j]=L[i][j-1]+1;
        }
        for(ll j=W-1;j>=0;j--){
            if(obstacle[i][j]){
                R[i][j]=-1;
                continue;
            }
            if(j==W-1)R[i][j]=0;
            else R[i][j]=R[i][j+1]+1;
        }
    }
    for(int j=0;j<W;j++){
        for(int i=0;i<H;i++){
            if(obstacle[i][j]){
                D[i][j]=-1;
                continue;
            }
            if(i==0)D[i][j]=0;
            else D[i][j]=D[i-1][j]+1;
        }
        for(ll i=H-1;i>=0;i--){
            if(obstacle[i][j]){
                U[i][j]=-1;
                continue;
            }
            if(i==H-1)U[i][j]=0;
            else U[i][j]=U[i+1][j]+1;
        }
    }
    ll ans=0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(obstacle[i][j]){
                continue;
            }
            ll sum=1+L[i][j]+R[i][j]+U[i][j]+D[i][j];
            if(sum>ans)ans=sum;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 126208
/*                    ___          |\    /|           ____   ____   ____  ____
   |     |    /\    /    \ |     | | \  / |    /\    |    \ |    \ |     |    \
   |_____|   /__\   \____  |_____| |  \/  |   /__\   |____/ |____/ |__   |____/
   |     |  /    \       \ |     | |      |  /    \  |      |      |     |   \
   |     | /      \ \____/ |     | |      | /      \ |      |      |____ |    \
*/
#include<bits/stdc++.h>
using namespace std;
#define lb lower_bound
#define ub upper_bound
#define pf push_front
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pi pair<int,int>
#define pl pair<long,long>
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define gc getchar_unlocked
#define pc putchar_unlocked
#define endl '\n'
#define loop(i,n) for(ll i=0;i<n;i++)
#define mod 1e9+7
#define in(x) scanf("%lld",&x)
#define in2(x,y) scanf("%lld %lld",&x,&y)
#define vl vector<ll>
#define vpll vector<pair<ll,ll>>
#define INF 0x3f3f3f3f
#define mp make_pair

ll calc(vl &dp,vl v,ll cost,ll pos, ll n) {
    if(dp[pos] == -1) {
        if(pos == n) return  dp[pos] = cost;
        if(pos == n-1) return dp[pos] = calc(dp,v,cost+abs(v[pos-1]-v[pos]),pos+1,n);
        dp[pos] = cost + min(calc(dp,v,abs(v[pos-1]-v[pos]),pos+1,n), calc(dp,v,abs(v[pos-1]-v[pos+1]),pos+2,n));
    }
    return dp[pos];
}

int main()
{
    ll n,k;
    if(in2(n,k)!=2) return 0;
    vl v(n),dp(n+1,INF);
    loop(i,n) in(v[i]);
    dp[n] = 0;
    dp[n-1] = abs(v[n-1]-v[n-2]);
    for(ll i=n-2;i>0;i--) {
        for(ll j=1;j<=k;j++)
            if(i+j<=n)
                dp[i] = min(dp[i+j] + abs(v[i-1]-v[i+j-1]),dp[i]);
    }
    cout<<dp[1]<<endl;
    // for(auto x:dp) cout<<x<<" ";
    return 0;
}

Measured memory_bytes: 1792
//Author: Fuadul Hasan(fuadul202@gmail.com)
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N   = 2e5 + 5;

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

	int a[n];

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

	//printf("%d\n", cnt);
	if(cnt == 1){
		cout<<-1<<endl;
	}
	else{
		cout<<n - (cnt-1)<<endl;
	}
	

	return 0;
}

Measured memory_bytes: 4420
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;


class FRangeSetQuery {
public:
    vector<int> c;

    template <class Abel> struct BIT {
        vector<Abel> dat[2];
        Abel UNITY_SUM = 0;                     // to be set

        /* [1, n] */
        BIT(int n) { init(n); }
        void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }

        /* a, b are 1-indexed, [a, b) */
        inline void sub_add(int p, int a, Abel x) {
            for (int i = a; i < (int)dat[p].size(); i += i & -i)
                dat[p][i] = dat[p][i] + x;
        }
        inline void add(int a, int b, Abel x) {
            sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
        }

        /* a is 1-indexed, [a, b) */
        inline Abel sub_sum(int p, int a) {
            Abel res = UNITY_SUM;
            for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
            return res;
        }
        inline Abel sum(int a, int b) {
            return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
        }

        /* debug */
        void print() {
            for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
            cout << endl;
        }
    };

    void solve(std::istream& cin, std::ostream& cout) {
        int N, Q;
        cin >> N >> Q;
        c.resize(N);
        REP(i, N) cin >> c[i];

        vector<int> lefts(Q), rights(Q), ids(Q);
        for (int i = 0; i < Q; ++i) {
            cin >> lefts[i] >> rights[i];
            --lefts[i];
            ids[i] = i;
        }
        sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});


        BIT<int> bit(N+5);
        vector<int> prev(N+1, -1);
        vector<int> res(Q, 0);
        int r = 0;
        for (auto i : ids) {
            for (; r < rights[i]; ++r) {
                bit.add(prev[c[r]]+2, r+2, 1);
                prev[c[r]] = r;
            }
            res[i] = bit.sum(lefts[i]+1, lefts[i]+2);
        }
        for (int i = 0; i < Q; ++i) cout << res[i] << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    FRangeSetQuery solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 35104
n = int(input())
aaa = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
sum_a = [0] * len(aaa)
sum_a[0] = aaa[0]
for i in range(n - 1):
    sum_a[i + 1] = sum_a[i] + aaa[i + 1]

for i in range(n):
    ans += aaa[i] * (sum_a[n -1] - sum_a[i])

print(ans%mod)


Measured memory_bytes: 31588
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//先ほどのプログラムと同様に共通部分文字列がわかれば、その他の部分を変えればいいだけでもない
//先ほどのプログラムにとらわれすぎた
//以下を参照した
//https://muttan1203.hatenablog.com/entry/2016/10/30/005158
//https://imulan.hatenablog.jp/entry/2015/10/31/181942
//https://takuti.me/note/levenshtein-distance/

//動的計画法
//部分問題でも同じ最適化問題が成立している
//部分問題間が独立している
//メモ化をするのか、部分問題を順に解いていくのか
//この問題ではメモ化

//編集距離dp[i][j]としてdp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+?)
//前半二つは削除と挿入(形的には変わらない)、置換は同じかどうかで違う
//どちらの要素に作用させるかだけなので
//?はiとjにあたる文字が同じなら0違うなら1


int main(){
  string s1,s2;
  int ls1,ls2;
  cin >> s1 >> s2;
  ls1=(int)(s1.size());ls2=(int)(s2.size());
  vector<vector<int>> dp(ls1,vector<int>(ls2,0));
  int k=0;
  for(int i=0;i<ls1;i++){
    if(s2[0]==s1[i]){
      k=1;
      dp[i][0]=i;
    }else if(k==1){
      dp[i][0]=i;
    }else{
      dp[i][0]=i+1;
    }
  }
  k=0;
  for(int i=0;i<ls2;i++){
    if(s1[0]==s2[i]){
      k=1;
      dp[0][i]=i;
    }else if(k==1){
      dp[0][i]=i;
    }else{
      dp[0][i]=i+1;
    }
  }
  for(int i=1;i<ls1;i++){
    for(int j=1;j<ls2;j++){
      int cost=1;
      if(s1[i]==s2[j]){cost=0;}
      dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost});
    }
  }

  cout << dp[ls1-1][ls2-1] << endl;
}



Measured memory_bytes: 6876
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

constexpr int M = 13333;
ll dp[M][2][111];

int main(int argc, char const *argv[]) {
    int d; string s; cin>>s>>d;
    int n = s.length();
    memset(dp,0,sizeof(dp));

    dp[0][0][0] = 1ll;

    rep(i,n) {
        int D = (int)(s[i]-'0');
        rep(j,2) {
            for (int x = 0; x <= (j?9:D); ++x) {
                rep(k,d) {
                    dp[i+1][j||(x < D)][(k+x)%d] = (dp[i+1][j||(x < D)][(k+x)%d]+dp[i][j][k])%MOD;
                }
            }
        }
    }


    cout << max(((dp[n][0][0]%MOD+dp[n][1][0]%MOD+MOD)-1ll)%MOD,0ll) << endl;

    return 0;
}

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

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

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

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

int cmp(int a, int b) {
    if (a == b) {
        return 0;
    }
    return a < b ? -1 : 1;
}

void solve() {
    int n, k;
    read(n, k);
    int ans = k;
    FOR(n - 1) {
        ans *= (k - 1);
    }
    print(ans);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
//    read(tt);
    FOR(tt) {
//        write("Case #", i + 1, ": ");
        solve();
    }
    
}



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

int main(){
    int a,b,c;
    int R=0;
    cin >>a>>b>>c;
    for (int x = a; x <= b; x++){
        if(c%x==0){
            R+=1;
        }
    }
    cout<<R<<endl;
    return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
constexpr int N = 18;
int n;
int a[N][2];
int dp[1 << N][N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i][0];
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i][1];
        if (i % 2 == 1)
            std::swap(a[i][0], a[i][1]);
    }
    for (int i = 0; i < (1 << n); ++i)
        std::fill(dp[i], dp[i] + n, -1);
    for (int i = 0; i < n; ++i)
        dp[1 << i][i] = 0;
    for (int s = 1; s < (1 << n) - 1; ++s) {
        int pos = __builtin_popcount(s) - 1;
        for (int i = 0; i < n; ++i) {
            if ((s >> i & 1) && dp[s][i] != -1) {
                int val = a[i][pos % 2];
                for (int j = 0; j < n; ++j) {
                    if ((~s >> j & 1) && a[j][(pos + 1) % 2] >= val) {
                        int t = s | 1 << j;
                        int tmp = dp[s][i] + pos + 1 - __builtin_popcount(s & ((1 << j) - 1));
                        if (dp[t][j] == -1 || dp[t][j] > tmp)
                            dp[t][j] = tmp;
                    }
                }
            }
        }
    }
    int ans = -1, s = (1 << n) - 1;
    for (int i = 0; i < n; ++i)
        if (dp[s][i] != -1 && (ans == -1 || ans > dp[s][i]))
            ans = dp[s][i];
    std::cout << ans << "\n";
    return 0;
}


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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n; cin >> n;
  vector<double> x(n),y(n); rep(i,n) cin >> x[i] >> y[i];
  vector<int> a(n);
  rep(i,n) a[i] = i;
  
  double ans = 0.0;
  int cnt = 0;
  do{
    /*vector<int> test(n);
    rep(i,n) test[i] = a[i];
    sort(test.begin(),test.end());
    test.erase(unique(test.begin(),test.end()),test.end());
    if(test.size()!=n) continue;*/

    double dist=0.0;
    rep(i,n-1){
      double tmp;
      tmp = (x[a[i]]-x[a[i+1]])*(x[a[i]]-x[a[i+1]])+(y[a[i]]-y[a[i+1]])*(y[a[i]]-y[a[i+1]]);
      tmp = sqrt(tmp);
      dist+=tmp;
    }
    ans += dist;
    //cout << ans << endl;
    cnt++;
  }while(next_permutation(a.begin(),a.end()));  

  ans = ans/(double)cnt;
  printf("%.10f\n",ans);
  
  return 0;
}


Measured memory_bytes: 3848
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

//https://atcoder.jp/contests/abc106/tasks/abc106_b

int main() {
    int N; cin >> N;
    if (N < 105) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0;
    for (int i = 107; i <= N; i=i+2) {
        int cnt = 0;
        for (int j = 1; j <= i; j=j+2) {
            if (i%j == 0) cnt++;
        }
        if (cnt == 8) ans++;
    }

    cout << ans + 1 << "\n";


    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Map<Integer,Integer> map = new HashMap<>();
        int[] sum = new int[n+1];
        long ans = 0;
        sum[0] = 0;
        map.put(0, 1);
        for(int i = 1; i < n+1; i++){
            sum[i] = (sum[i-1] + sc.nextInt()) % m;
            if(!map.containsKey(sum[i])){
                map.put(sum[i], 1);
            }else{
                map.put(sum[i], map.get(sum[i]) + 1);
            }
            ans += map.get(sum[i]) - 1;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 60796
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Adjacents solver = new Adjacents();
        solver.solve(1, in, out);
        out.close();
    }

    static class Adjacents {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int n = in.nextInt();
            int count = 0;
            int two = 0;
            for (int i = 0; i < n; i++) {
                int cur = in.nextInt();
                if (cur % 4 == 0) ++count;
                else if (cur % 2 == 0) two++;
            }
            count += two / 2;
            out.println(count < n / 2 ? "No" : "Yes");
        }

    }

    static class FastReader {
        BufferedReader reader;
        StringTokenizer st;

        public FastReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    if (line == null) {
                        return null;
                    }
                    st = new StringTokenizer(line);
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



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

int main()
{
  int n;
  int k;
  cin >> n >> k;
  int h[n];
  int ans=0;
  for(int i=0;i<n;++i){
    cin >> h[i];
    if(h[i]>=k){
      ++ans;
    }
  }

  cout << ans;
  
  return 0;
}

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

}

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

fn main(){
    let line = read_as_vec::<usize>();
    let (n, c, k) = (line[0], line[1] as u64, line[2] as u64);

    let mut t: Vec<u64> = vec![];
    for _ in 0..n{
        t.push(read_as_vec()[0]);
    }

    t.sort();

    let mut i = 0;
    let mut ans = 0;
    while i < n{
        let depart_timelimit = t[i] + k;
        let mut passengers = 0;
        while i < n && passengers < c && t[i] <= depart_timelimit {
            passengers += 1;
            t[i] = 0;
            i += 1;
        }
        if i == n{
            if passengers > 0{
                ans += 1;
            }
            break;
        }
        ans += 1;
    }

    println!("{}", ans);
}


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

int main() {
	string s; 
	cin >> s;
	int temp = 0, ct = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'A' || s[i] == 'G' || s[i] == 'C' || s[i] == 'T') {
			temp++;
			if (temp > ct)
				ct = temp;
		}
		else {
			temp = 0;
		}
	}
		cout << ct;
	return 0;
}



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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(reader.readLine());
    int[] h = new int[N + 1];
    String[] line = reader.readLine().split(" ");
    for(int i = 1; i <= line.length; i++){
      h[i] = Integer.parseInt(line[i-1]);
    }
    if( N == 2){
      System.out.println(h[2] - h[1]);
      return;
    }
    int[] dp = new int[N + 1];
//    dp[0] =
    dp[2] = Math.abs(h[2] - h[1]);
    for (int i = 3; i <= N; i++){
      dp[i] = Math.min(dp[i - 1] + Math.abs(h[i] - h[i - 1]),
              dp[i - 2] + Math.abs(h[i] - h[i - 2]));
    }
//    System.out.println(Arrays.toString(dp));
    System.out.println(dp[N]);

  }
}


Measured memory_bytes: 35536
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,a[N],sum;
bitset<N*N> dp;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
	dp[0]=1;
	for (int i=1;i<=n;i++)dp|=dp<<a[i];
	for (int i=(sum+1)/2;i;i++)
		if (dp[i]){
			printf("%d\n",i);
			return 0;
		}
}

Measured memory_bytes: 1664
// Problem : C - Ubiquity
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)


/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、 
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/

// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define bug(x) cout<<#x<<"="<<x<<endl; 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; //check the limits, dummy
 ll mod_pow(ll x,ll n) {
	if (n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n / 2);
	if (n & 1) res = res * x % MOD;
	return res;
}

ll comb(ll n, ll x) {
	ll ret = 1,k=1;
	F0R(i,x)ret = (ret * (n - i))%MOD;
	F0R(i,x)k = (k * (x-i))%MOD;
	k = mod_pow(k, MOD - 2);
	ret = (ret*k + MOD) % MOD;
	return ret;
}
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);    
	ll N;
	cin>>N;	
	
	ll ans=mod_pow(10,N)-2*mod_pow(9,N)+mod_pow(8,N);
	// ans=N*(N-1)*mod_pow(10,N-2);
	ans+=10*(ll)MOD;
	ans%=MOD;
	cout<<ans<<nl;
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 3636
from math import tan, pi

a, b, x = list(map(float, input().split()))
eps = 1e-9

def f(a, b, theta):
    if theta > pi / 2.0 - eps:
        return  0.0
    ret = 0.0
    if a * tan(theta) <= b:
        ret = a * a * b - a * a * a * tan(theta) / 2.0
    else:
        ret = b * b / tan(theta) * a / 2.0
    return ret

def solve():
    ok = pi / 2.0
    ng = 0.0
    for _ in range(100000):
        mid = (ok + ng) / 2.0
        if f(a, b, mid) < x:
            ok = mid
        else:
            ng = mid
    print("{:.10f}".format(ok / pi * 180))

solve()

Measured memory_bytes: 38896
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

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

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  ll a, b; cin >> a >> b;
  ll c, d; cin >> c >> d;

  ll ans = -1e18;
  chmax(ans, a * c);
  chmax(ans, b * d);
  chmax(ans, a * d);
  chmax(ans, b * c);

  if (a <= 0 && b >= 0) chmax(ans, 0);
  if (c <= 0 && d >= 0) chmax(ans, 0);

  cout << ans << endl;
  
  return (0);
}

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

int main() {
  int A, B, s = -1;
  cin >> A >> B;
  for(int i = 1; i <= 1250; i++) {
    if(i*8/100 == A && i*10/100 == B) {
      s = i;
      break;
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

using namespace std;

long long L;
int N;
long long X[400001];
long long S[400002];
long long ans;

void solve() {
    for (int i = 0; i <= N * 2; i++) {
        S[i + 1] = S[i] + X[i];
    }
    for (int i = N; i >= 0; i--) {
        long long c = 0;
        c += (S[N+(i+2)/2]-S[N])-(S[i+1]-S[i+1-(i+2)/2]);
        c += (S[N+1+(i+1)/2]-S[N+1])-(S[i+1]-S[i+1-(i+1)/2]);
        ans = max(ans, c);
    }
}

int main() {
    scanf("%lld %d", &L, &N);
    X[N] = L;
    for (int i = 0; i < N; i++) {
        scanf("%lld", &X[i]);
        X[N + i + 1] = X[i] + L;
    }
    solve();
    for (int i = 0; i <= N * 2; i++) {
        X[i] = 2*L - X[i];
    }
    reverse(X, X + N*2+1);
    solve();
    printf("%lld\n", ans);
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  int T;
  T = 1;
  while (T--) solve();
}

void solve() {
  vector<int> v({1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51});
  int k;
  cin >> k;
  cout << v[k - 1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    string S;
    unsigned long long K;
    cin >> S >> K;
    for (int i = 0; i < S.size(); i++) {
        if ('2' <= S[i] && S[i] <= '9') {
            cout << S[i >= K ? K-1 : i] << endl;
            return 0;
        }
    }
    cout << S[K-1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
   int money,maisuu,charge;
   cin >> money;
   if(money % 1000 == 0){
       maisuu = money /1000;
   }else{
     maisuu = (money / 1000)+1;  
   } 
   charge = (maisuu*1000)-money;
   
   cout << charge << endl;
    
}


Measured memory_bytes: 3536