akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int ret;

void dfs(int idx, bool flg, const vector<int>& A){
  if(idx >= A.size()){
    if(flg) ret++;
    return;
  }
  
  int v = A[idx];
  if(flg){
    dfs(idx+1, true, A);
    dfs(idx+1, true, A);
    dfs(idx+1, true, A);
  }else{
    if((v-1)%2==0) dfs(idx+1, true, A);
    else dfs(idx+1, false, A);
    if(v%2==0) dfs(idx+1, true, A);
    else dfs(idx+1, false, A);
    if((v+1)%2==0) dfs(idx+1, true, A);
    else dfs(idx+1, false, A);
  }
}


int main(){
  int N;
  cin >> N;
  vector<int> A;
  rep(i,N){
    int a;
    cin >> a;
    A.push_back(a);
  }

  ret = 0;
  dfs(0,false,A);
  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    x = LI()
    q = 0
    ans = 1
    for i in range(n):
        q += 1
        if x[i] < 2 * q - 1:
            ans *= q
            ans %= mod
            q -= 1
    for i in range(q):
        ans *= i + 1
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


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

public class Main {
  private static void execute(ContestReader reader, PrintWriter out) {
    out.println(reader.nextInt() < 1200 ? "ABC" : "ARC");
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 20564
r, c = map(lambda x: int(x), input().split(" "))
table = []
total = [0] * (c + 1)
for i in range(r):
    row = list(map(lambda x: int(x), input().split(" ")))
    row.append(sum(row))
    table.append(row)
    total = [x + y for (x, y) in zip(total, row)]
table.append(total)
for row in table:
    print(" ".join(map(lambda x: str(x), row)))



Measured memory_bytes: 5704
import copy
MOD = 10**9+7
s = list(input())
n = len(s)
s.reverse()
dp = []
tem = []
for i in range(13):
    tem.append(0)
for i in range(n+1):
  dp.append(copy.copy(tem))
dp[0][0]=1
beki = 1
for i in range(1,n+1):
    if s[i-1] != "?":
        s1 = int(s[i-1])
        k = (s1*beki)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
            #print(dp[i][(j+k)%13])
            dp[i][(j+k)%13]%=MOD
    else:
        for j in range(10):
            k = (j*beki)%13
            for x in range(13):
                dp[i][(x+k)%13] += dp[i-1][x]
                dp[i][(x+k)%13]%=MOD
    beki=beki*10
    beki%=13
    #print(dp[i])
print(dp[n][5])


Measured memory_bytes: 65400
n = int(input())
an = list(map(int,input().split()))
bn = list(map(int,input().split()))
cn = list(map(int,input().split()))
st = sum(bn)
for i in range(0, n-1):
    if an[i] == an[i+1] - 1:
        st += cn[an[i]-1]
print(st)

Measured memory_bytes: 3064
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}
using namespace std;
typedef long long ll;
ll gcd(ll, ll);
vector<bool> to_binary(int);
int sum(vector<int>);
int min(vector<int>);
int max(vector<int>);
ll nCr(ll n, ll r);

const ll INF = 1LL << 60;

typedef tuple<ll, ll> mtupl;

bool mycomp(mtupl x, mtupl y) {
	return get<1>(x) < get<1>(y);
}

vector<vector<ll>> memo;

ll get(int x, int y) {
	if (memo[x][y] != -1)
		return memo[x][y];

	if (x == 0) return 1;
	if (y < x) return 0;

	memo[x][y] = get(x, y - 1) + get(x - 1, y - 1);
	return memo[x][y];
}

ll mpow(ll a, ll b) {
	ll ans = 1;
	for (ll i = 0; i < b; i++) {
		ans *= a;
		ans %= 1000000007;
	}
	return ans;
}

ll nCr(ll n, ll r) {
	ll res = 1;
	for (int i = 0; i < r; i++) {
		res *= (n - i);
	}
	for (int i = 1; i <= r; i++) {
		res /= i;
	}
	return res;
}

int vsum(vector<int> v) {
	int res = 0;
	for (auto it = v.begin(); it != v.end(); it++)
		res += *it;
	return res;
}
int vmin(vector<int> v) {
	int min = INT32_MAX;
	for (auto it = v.begin(); it != v.end(); it++)
		min = std::min(min, *it);
	return min;
}
int vmax(vector<int> v) {
	int max = 0;
	for (auto it = v.begin(); it != v.end(); it++)
		max = std::max(max, *it);
	return max;
}

ll gcd(ll A, ll B) {
	if (A == 0 || B == 0) return max(A, B);
	int r = A % B;
	while (r != 0) {
		A = B;
		B = r;
		r = A % B;
	}

	return B;
}

vector<bool> to_binary(int x) {
	vector<bool> res;
	while (x != 0) {
		res.push_back(x % 2);
		x /= 2;
	}
	return res;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Program Start	

	string S;
	cin >> S;

	int ans = 0;
	rep(i, 4)
		if (S[i] == '+')ans++;
		else ans--;

	cout << ans << endl;

ProgramEndPointLabel:;

	//Program End
	system("pause");

	return 0;
}




Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define ITR 100

ll N;
vector<ll> vx, vy;

double f(double x, double y){
    double ret = 0;
    rep(i, 0, N){
        double dx = x - vx[i];
        double dy = y - vy[i];
        ret = max(ret, sqrt(dx*dx + dy*dy));   
    }
    return ret;
}

double g(double x){
    double L = -1000, R = 1000;
    rep(itr, 0, ITR){
        double m1 = (L * 2 + R) / 3;
        double m2 = (L + R * 2) / 3;
        if(f(x, m1) > f(x, m2)) L = m1;
        else R = m2;
    }
    return f(x, L);
}

int main(){
    cin >> N;
    vx.resize(N);
    vy.resize(N);
    rep(i, 0, N) cin >> vx[i] >> vy[i];

    double L = -1000, R = 1000;
    for(ll itr = 0; itr < ITR; itr++){
        double m1 = (L * 2 + R) / 3;
        double m2 = (L + R * 2) / 3;
        if(g(m1) > g(m2)) L = m1;
        else R = m2;
    }

    printf("%.20lf\n", g(L));
    return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    abc151d()
}

fun abc151d() {
    val (h, w) = readLine()!!.split(' ').map { it.toInt() }
    val isRoad = (1..h).map { readLine()!!.map { it == '.' }.toBooleanArray() }.toTypedArray()

    data class Coordinate(val y: Int, val x: Int)

    val INF = 1000000
    val direction = listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)
    val minCosts = Array(500) { y -> IntArray(500) { x -> if (y == x) 0 else INF } }
    fun getId(y: Int, x: Int) = y * w + x

    for (y in 0 until h) {
        for (x in 0 until w) {
            if (!isRoad[y][x]) continue
            direction.map { Coordinate(y + it.first, x + it.second) }
                .filter { it.y in 0 until h && it.x in 0 until w && isRoad[it.y][it.x] }
                .forEach { minCosts[getId(y, x)][getId(it.y, it.x)] = 1 }
        }
    }

    val gridSize = h * w

    for (k in 0 until gridSize)
        for (i in 0 until gridSize)
            for (j in 0 until gridSize)
                minCosts[i][j] = Math.min(minCosts[i][j], minCosts[i][k] + minCosts[k][j])

    val answer = minCosts.map { it.filter { it < INF }.max() ?: 0 }.max() ?: 0

    println(answer)
}


Measured memory_bytes: 41544
import java.io.*;
import java.util.*;
class Main
{
  public static void main(String args[])throws Exception
  {
    Scanner Sc=new Scanner(System.in);
    int n=Sc.nextInt();
    double sum=0;
    double product=1;
    int a[]=new int[n];
    for(int i=0;i<n;i++)
    {
      a[i]=Sc.nextInt();
      product=product*a[i];
    }
    for(int i=0;i<n;i++)
    {
      sum=sum+(product/a[i]);
    }
    sum=product/sum;
    System.out.println(sum);
  }
}

Measured memory_bytes: 21844
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,i;
	double ans=0;
    cin>>n>>k;
    for(i=1;i<=n;i++)
        if(i>=k) 
			ans+=1.0/n;
        else
		{
            int tmp=i,cnt=0;
            while(tmp<k)
            {
				tmp*=2;
				cnt++;
			}
            ans+=1.0/n*pow(0.5,(double)cnt);
        }
    cout<<fixed<<setprecision(9)<<ans;
    return 0;
}

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

    let n = read::<u32>();

    let mut prices: Vec<i32> = Vec::new();
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        let price = s.trim().parse().ok().unwrap();
        prices.push(price);
    }

    // println!("n = {}", n);
    // for p in &prices {
    //     print!("{} ", p);
    // }

    let mut r_min = prices[0];
    let mut max_profit: i32 = -2_000_000_000;
    for i in 1..prices.len() {
        max_profit = std::cmp::max(max_profit, prices[i] - r_min);
        r_min = std::cmp::min(r_min, prices[i]);
    }

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



Measured memory_bytes: 5044
#include<cstdio>
#include<array>
using namespace std;
const int MAX_V = 100;
array<array<int,MAX_V>,MAX_V> ary{0};
int main(){
  int n;scanf("%d",&n);
  for(int i=0;i<n;i++){
    int u;scanf("%d",&u);
    int k;scanf("%d",&k);
    for(int j=0;j<k;j++){
      int v;scanf("%d",&v);
      ary[v-1][u-1]=1;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      printf(j==n-1?"%d\n":"%d ",ary[j][i]);
    }
  }
}

Measured memory_bytes: 1044
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
int n, m, v, p;
int a[N];
bool check(int x)
{
	if(a[x]+m<a[p]) return 0;
	int have = p-1+n-x+1;
	if(have>=v) return 1;
	ll need = 0;
	for(int i=p; i<x; i++)
		need += (a[x]+m-a[i]);
	return need>=1ll*(v-have)*m;
}
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> m >> v >> p;
 	for(int i=1; i<=n; i++) cin >> a[i];
 	sort(a+1, a+n+1);
 	reverse(a+1, a+n+1);
 	int l = p+1, r = n, ans = p;
 	while(l<=r)
 	{
 		int mid = (l+r)>>1;
 		if(check(mid)) l = mid+1, ans = mid;
 		else r = mid-1;
 	}
 	cout << ans;
	return 0;
}


Measured memory_bytes: 640
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	alice, bob := 0, 0
	for i := range a {
		if i%2 == 0 {
			alice += a[i]
			continue
		}
		bob += a[i]
	}
	fmt.Println(alice - bob)
}


Measured memory_bytes: 512
#include <iostream>
#define ll long long
using namespace std;
const int N = 5009;
int n,k;
int p[N],c[N],sp[N],avail[N];
long long f[N][N];
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++){
        memset(avail,0,sizeof(avail));
        int j = i , cnt = 0;
        while (avail[p[j]] == 0){
            cnt++;
            f[i][cnt] = f[i][cnt - 1] + c[p[j]];
            avail[p[j]] = 1;
            j = p[j];
        }
        sp[i] = cnt;
    }
    ll ans = -1e18;
    for (int i = 1; i <= n; i++){
        ll pos_max = 0 , val = -1e18;
         for (int j = 1; j <= min(k,sp[i]); j++)
            if (f[i][j] > val){
                val = f[i][j];
                pos_max = j;
            }
        ans = max(ans,f[i][pos_max] + max(0LL,1LL * ((k - pos_max)/sp[i]) * f[i][sp[i]]));
        ans = max(ans,1LL * (k/sp[i]) * f[i][sp[i]] + f[i][k % sp[i]]);
    }
    cout << ans;
}

Measured memory_bytes: 198920
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ
char in[210000];
int cnt[3100];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	long long ret=0;
	int cur=0;
	int ks=1;
	for(int i=n-1;i>=0;i--){
		// printf("%d %d\n",cur,cnt[cur]);
		cnt[cur]++;
		cur=(cur+ks*(in[i]-'0'))%2019;
		ks=ks*10%2019;
		ret+=cnt[cur];
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 1888
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=100005,mod=1e9+7;
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n;
int a[N],s[N];
void IN(){
	char s[N];
	cin>>s+1;
	n=strlen(s+1);
	For(i,1,n)
		a[i]=s[i]-'a'+1;
}
int p[3];
int b1[N],b2[N];
int dp[N];
int ans=0;
int main(){
	IN();
	For(i,0,2)
		p[i]=n+1;
	For(i,1,n)
		s[i]=(s[i-1]+a[i])%3;
	int las=n;
	Fod(i,n,1){
		if (i<n&&a[i]==a[i+1]){
			Fod(j,las,i+1)
				p[s[j]]=j;
			las=i;
		}
		if (a[i]==1)
			b1[i-1]=i,b2[i-1]=p[(s[i-1]+2)%3];
		else
			b2[i-1]=i,b1[i-1]=p[(s[i-1]+1)%3];
	}
	if (las==n)
		return puts("1"),0;
	dp[0]=1;
	For(i,0,n-1){
		Add(dp[b1[i]],dp[i]);
		Add(dp[b2[i]],dp[i]);
	}
	For(i,1,n)
		if ((s[n]-s[i]+3)%3==0)
			Add(ans,dp[i]);
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	string s; cin>>s;
	char c=s[0];
	if(c==s[1] && c==s[2]) cout<<"No";
	else cout<<"Yes";
	return 0;
}


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

int dp[100004], N, ar[100004], K;

int rec(int pos){
  if(pos == N-1) 
    return 0;
  if(dp[pos]!=-1)
    return dp[pos];
  int ans = 1000000000;
  for(int i=pos + 1;i<=pos+K && i<N;++i) {
    ans = min(ans, abs(ar[i] - ar[pos]) + rec(i));
  }
  dp[pos] = ans;
  return dp[pos];
}

int main() {
  scanf("%d %d",&N, &K);
  for(int i=0;i<N;++i){
  	scanf("%d",&ar[i]);
  }
  memset(dp, -1, sizeof(dp));
  printf("%d",rec(0));
  return 0;
}

Measured memory_bytes: 5760
#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 27;
const double EPS = 1e-10;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
#define repD(i, n) for(int i = n; i >= 0; i--)

int block[102][102];
bool visit[102][102];


int main(){
	int n, w, h, xs, ys, xg, yg;
	int c, d, x, y;
	while(cin >> w >> h && (w || h)){
		cin >> xs >> ys;
		cin >> xg >> yg;
		fill(&block[0][0], &block[101][101] + 1, -1);
		memset(visit, false, sizeof(visit));
		cin >>n;
		rep(i, n){
			cin >> c >> d >> x >> y;
			if(d){
				rep(j, 4) rep(k, 2) block[x+k][y+j] = c;
			}else{
				rep(j, 4) rep(k, 2) block[x+j][y+k] = c;
			}
		}

		queue<P> que;
		que.push(P(xs, ys));
		visit[xs][ys] = true;
		int dx[] = {1, 0, -1, 0};
		int dy[] = {0, -1, 0, 1};
		
		while(!que.empty()){
			P p = que.front();
			que.pop();
			x = p.first;
			y = p.second;
			rep(i, 4){
				int x2 = x + dx[i];
				int y2 = y + dy[i];
				if(!visit[x2][y2] && block[x2][y2] == block[x][y]){
					visit[x2][y2] = true;
					que.push(P(x2, y2));
				}
			}
		}

		if(visit[xg][yg]) cout << "OK" << endl;
		else cout << "NG" << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
#include <string>
int main() {
    int sum=0,i;
	string s;
	cin>>s;
	if(s.length()==3)
	{
	    for(i=0;i<s.length();i++)
	    {
	        if(s[i]==s[i+1])
	        sum++;
	    }
	    if(sum==2)
	    {
	        cout<<"No"<<endl;
	    }
	    else
	    cout<<"Yes"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[4][4];
	int n;
	memset(a,0,sizeof(a));
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			cin>>a[i][j];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int t; 
		cin>>t;
		for(int i=1;i<=3;i++)
		{
			for(int j=1;j<=3;j++)
			{
				if(a[i][j]==t) a[i][j]=1;
			}
		}
	}
	for(int i=1;i<=3;i++)
	{
		if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][1]==1)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
		if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[2][i]==1)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	if(a[1][1]==a[2][2]&&a[2][2]==a[3][3])
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	if(a[1][3]==a[2][2]&&a[2][2]==a[3][1]&&a[1][3]==1)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
    return 0;
 } 

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

int main(){
    ll n,m;
    cin >> n >> m;
    ll ans = 0;
    if(n*2 > m){
        ans += m/2;
    }
    else{
        ans += n;
        m -= n*2;
        ans += m/4;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main( void ) {
	int n, y, m, d, tmp;

	scanf( "%d", &n );
	while ( n-- ) {
		scanf( "%d %d %d", &y, &m, &d );
		y--;
		m--;
		d--;

		tmp = y / 3 * 590 + y % 3 * 195 + d;
		if ( ( y + 1 ) % 3 )
			tmp += m / 2 * 39 + m % 2 * 20;
		else
			tmp += m * 20;

		printf( "%d\n", 196470 - tmp );
	}

	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

ll N=2e5+10;

int main() {
  ll n;
  cin >> n;
  vec x(n),y(n);
  vector<char> p(n);
  vector<set<ll>> u(N),d(N),l(N),r(N);
  for(ll i=0;i<n;i++) {
    cin >> x[i] >> y[i] >> p[i];
    if(p[i]=='U') {
      u[x[i]].insert(y[i]);
    }
    if(p[i]=='D') {
      d[x[i]].insert(y[i]);
    }
    if(p[i]=='L') {
      l[y[i]].insert(x[i]);
    }
    if(p[i]=='R') {
      r[y[i]].insert(x[i]);
    }
  }
  ll ans=inf;
  for(ll i=0;i<N;i++) {
    if(u[i].size()==0||d[i].size()==0) continue;
    for(ll f:u[i]) {
      auto it=d[i].upper_bound(f);
      if(it==d[i].end()) continue;
      ans=min(ans,(*it-f)*5);
    } 
  }
  for(ll i=0;i<N;i++) {
    if(r[i].size()==0||l[i].size()==0) continue;
    for(ll f:r[i]) {
      auto it=l[i].upper_bound(f);
      if(it==l[i].end()) continue;
      ans=min(ans,(*it-f)*5);
    } 
  }
  N*=2;
  vector<set<ll>> tu(N),td(N),tl(N),tr(N);
  for(ll i=0;i<n;i++) {
    ll v=x[i]-y[i]+N/2;
    if(p[i]=='U') {
      tu[v].insert(y[i]);
    }
    if(p[i]=='D') {
      td[v].insert(x[i]);
    }
    if(p[i]=='L') {
      tl[v].insert(y[i]);
    }
    if(p[i]=='R') {
      tr[v].insert(x[i]);
    }
  }
  for(ll i=0;i<N;i++) {
    if(tu[i].size()==0||tl[i].size()==0) continue;
    for(ll f:tu[i]) {
      auto it=tl[i].upper_bound(f);
      if(it==tl[i].end()) continue;
      ans=min(ans,(*it-f)*10);
    }
  }
  for(ll i=0;i<N;i++) {
    if(tr[i].size()==0||td[i].size()==0) continue;
    for(ll f:tr[i]) {
      auto it=td[i].upper_bound(f);
      if(it==td[i].end()) continue;
      ans=min(ans,(*it-f)*10);
    }
  }
  vector<set<ll>> su(N),sd(N),sl(N),sr(N);
  for(ll i=0;i<n;i++) {
    ll v=x[i]+y[i];
    if(p[i]=='U') {
      su[v].insert(y[i]);
    }
    if(p[i]=='D') {
      sd[v].insert(y[i]);
    }
    if(p[i]=='L') {
      sl[v].insert(y[i]);
    }
    if(p[i]=='R') {
      sr[v].insert(y[i]);
    }
  }
  for(ll i=0;i<N;i++) {
    if(su[i].size()==0||sr[i].size()==0) continue;
    for(ll f:su[i]) {
      auto it=sr[i].upper_bound(f);
      if(it==sr[i].end()) continue;
      ans=min(ans,(*it-f)*10);
    }
  }
  for(ll i=0;i<N;i++) {
    if(sd[i].size()==0||sl[i].size()==0) continue;
    for(ll f:sl[i]) {
      auto it=sd[i].upper_bound(f);
      if(it==sd[i].end()) continue;
      ans=min(ans,(*it-f)*10);
    }
  }
  if(ans==inf) cout << "SAFE" << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 222048
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <cstdio>
#include <deque>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;
bool c[10000001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int s; cin >> s;
	c[s] = true;
	int ans = 1;
	while (1) {
		if (s & 1) {
			s = 3 * s + 1;
		}
		else {
			s = s / 2;
		}
		ans += 1;
		if (c[s])break;
		c[s] = true;
	}
	cout << ans << '\n';


}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

    int a,b;

    scanf("%d %d",&a,&b);
    if(a<b){
        printf("a < b\n");
    }
    if(a>b){
        printf("a > b\n");
    }
    if(a==b){
        printf("a == b\n");
    }
    return 0;
}

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

int main(){
    int n;
    cin>>n;
    map<string,int> mp;
    int cnt =0;
    rep(i,n){
        string s;
        cin>>s;
        mp[s]++;
        if (mp[s]>1) cnt ++;
    }
    cout << n-cnt;
}


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

#define MX 1000
const long long M=1e9+7;

int w, h;
string tab[MX+5];
long long dp[MX+5][MX+5];

long long saf( int x, int y )
{
  if( x<0 or y<0 ) return 0;
  return dp[x][y];
}

int main( )
{
  cin>>h>>w;
  for( int i=0; i<h; i++ )
    cin>>tab[i];

  dp[0][0]=1;
  for( int i=0; i<h; i++ )
  {
    for( int j=0; j<w; j++ )
    {
      if( tab[i][j]!='#' ) dp[i][j]=( max( dp[i][j], saf(i,j-1)+saf(i-1,j) ) )%M;
    }
  }

  cout<<dp[h-1][w-1]<<"\n";
}


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

int main() {

    int n;

    cin >> n;

    vector<int> blocks;
    int breakCount = 0;

    blocks.push_back(-1);

    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        blocks.push_back(num);
    }

    int i = 1;
    int index = 1;

    while(index <= n) {
        
        while(index <= n && blocks[index] != i) {
            breakCount++;
            index++;
        }

        if(index != n + 1)
            i += 1;
        index += 1;

    }
    

    if(i == 1 && breakCount != 0) {
        cout << -1 << endl;
    }
    else 
        cout << breakCount << endl;

    return 0;

}

Measured memory_bytes: 1400
S = input()

maxcnt = 0
cnt = 0
for b in S:
  if (b == "A") or (b == "C") or (b == "G") or (b == "T"):
    cnt += 1
  else:
    cnt = 0
  if cnt > maxcnt:
    maxcnt = cnt

print(maxcnt)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;

ll mod = 998244353;
const double error = 1e-7;
const double PI = acos(-1); //const ld PI = acosl(-1)

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define eq(x, y) (fabs((x)-(y))<error)
#define bt(i) (1LL<<(i))

#define debug(x) cerr<<#x<<" = "<<(x)<<"\n"
#define hoise cerr<<"hoise\n"
#define tham getchar()
mt19937 rng((unsigned int) chrono::system_clock::now().time_since_epoch().count());

inline ll MOD(ll x, ll m = mod)
{
    ll y = x % m;
    return (y >= 0) ? y: y+m;
}

const int inf = 1e9+5;
const ll infl = 1e18+1;
const int nmax = 2e5+5;
///====================== template =========================

int main(){
    FASTIO;
    int tc;
    cin>>tc;
    for(int cs = 1; cs<=tc; cs++){
        ll a, b, c, d;
        cin>>a>>b>>c>>d;

        if(a < b) {
            cout<<"No\n";
            continue;
        }

        a %= b;

        if(a > c){
            cout<<"No\n";
            continue;
        }

        ll del = d - b;
        if(del < 0){
            cout<<"No\n";
            continue;
        }

        if(del == 0){
            cout<<"Yes\n";
            continue;
        }

        del = __gcd(del, b);

        if((b-a+del-1)/del - (c-a)/del > 1){
            cout<<"No\n";
        }
        else{
            cout<<"Yes\n";
        }
    }

}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3

int M[1400][1400];
int dp[1400][1400] = {};

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

int main()
{
	int H, W, ans = 1;
	cin >> H >> W;
	REP(i, H)REP(j, W)cin >> M[i][j];
	REP(i, H)REP(j, W)
	{
		if (M[i][j] == 0)break;
		else if (i == H - 1 && j == W - 1 && M[i][j] == 1)ans = 0;
	}
	REP(i, W)if (M[0][i] == 0)dp[0][i] = 1;
	REP(i, H)if (M[i][0] == 0)dp[i][0] = 1;
	FOR(i, 1, H)FOR(j, 1, W)
	{
		if (M[i][j] == 1)continue;
		int temp = INF;
		REP(k, 3)temp = min(temp, dp[i+dy[k]][j+dx[k]]);
		dp[i][j] = temp + 1;
		ans = max(ans, dp[i][j]);
	}
	cout << ans*ans << endl;
	return 0;
}

Measured memory_bytes: 16136
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using tiii = tuple<int,int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
int main(){
  ll x,y,z,k; cin >> x >> y >> z >> k;
  vector<ll> a(x),b(y),c(z);
  rep(i,x) cin >> a[i]; rep(i,y)  cin >> b[i]; rep(i,z) cin >> c[i];
  sort(ALL(a), greater<ll>()),sort(ALL(b), greater<ll>()),sort(ALL(c),greater<ll>());
  vector<ll> ab; rep(i,x)rep(j,y) ab.pb(a[i] + b[j]);
  sort(ALL(ab),greater<ll>());
  vector<ll> abc;
  rep(i,min(k,x*y))rep(j,z){
    abc.pb(ab[i] + c[j]);
  }
  sort(ALL(abc),greater<ll>());
  rep(i,k)cout << abc[i] << endl;
}

Measured memory_bytes: 43240
#include<cstdio>
using namespace std;
const int INF = 1000000000;

int h, w;
int m[1000][1000];
int d[1000][1000]; // ok => INF - 1, one => number, zero => imposible, INF => not check yet
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int check(int y, int x) {
  if (d[y][x] != INF) return d[y][x];
  int temp = 0;
  for (int k = 0; k < 4; k++) {
    int ny = y + dy[k], nx = x + dx[k];
    if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
    if (m[y][x] > m[ny][nx]) {
      int t = check(ny, nx);
      if (t == INF - 1) return d[y][x] = INF - 1;
      if (temp) {
        if (t == 0 && temp != m[ny][nx]) return d[y][x] = INF - 1;
        if (t != 0 && temp != t) return d[y][x] = INF - 1;
      } else {
        if (t == 0) temp = m[ny][nx];
        else temp = t;
      }
    }
  }
  return d[y][x] = temp;
}

int main() {
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) scanf("%d", &m[i][j]);
  for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) d[i][j] = INF;
  int ans = 0;
  for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (check(i, j) == INF - 1) ans++;
  printf("%d\n", ans);
}



Measured memory_bytes: 49416
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

	int N=in(),K=in();
	double base = (N>=K) ? ((double)(N-K))/N : 0.0;
	vector<int> tnum;
	for(int i=0,ei=min(K,N);i<ei;i++){
		int v=i+1,num=0;
		while(v<K){
			v*=2;
			num++;
		}
		tnum.push_back(num);
	}

	int sum=0,div=0;
	double add = 0.0;
	if(!tnum.empty()){
		div = tnum[0];
		for(auto& x:tnum) sum += pow(2.0,(double)(div-x));
		add = ((double)sum)/pow(2.0,(double)div);
		add *= 1.0/(double)N;
	}
	add+=base;
	cout << fixed;
	cout << setprecision(16);
	cout << add << endl;
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

ll dp[3001][4]={};

int main() {

	int r,g,b,n;
	cin>>r>>g>>b>>n;


	if(r<=n)dp[r][1]++;
	if(g<=n)dp[g][2]++;
	if(b<=n)dp[b][3]++;

	for(int j=1; j<=3; j++){
		int t;
		if(j==1)t=r;
		if(j==2)t=g;
		if(j==3)t=b;
		for(int i=1; i<=n; i++){
			dp[i][j]+=dp[i][j-1];
			if(dp[i][j]==0)continue;
			if(i+t<=n)dp[i+t][j]+=dp[i][j];
		}
	}
	cout<<dp[n][3]<<endl;

	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
using ll = long long;
int main() {
    ll h,w;
    cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1 << endl;
    }else{
        cout << (h*w+1)/2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>

#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#include <iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll mod = 1e9 + 7;



string S;

ll N,ans;
ll A[51], B[51];

int main() {

	cin >> N;
	
	FOR(i, 0, N) {
		cin >> A[i];
		B[i] = A[i];
	}
	sort(A, A + N);
	int cnt = 0;
	FOR(i, 0, N) {
		if (A[i] != B[i])cnt++;
	}
	if (cnt <= 2)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  cin >> n;
  vi t(n + 1), x(n + 1), y(n + 1);
  t[0] = x[0] = y[0] = 0;
  rep2(i, 1, n + 1) cin >> t[i] >> x[i] >> y[i];
  bool ok = true;
  rep2(i, 1, n + 1) {
    if(t[i] % 2 != (x[i] + y[i]) % 2) ok = false;
    int dt = t[i] - t[i - 1];
    int dx = x[i] - x[i - 1];
    int dy = y[i] - y[i - 1];
    if(dt < dx + dy) ok = false;
  }
  cout << (ok ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1408
n,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(1,n):
    for k in range(1,K+1):
        if i-k>=0:
            dp[i] = min(dp[i],dp[i-k] + abs(h[i-k] - h[i]))
print(dp[n-1])

Measured memory_bytes: 55392
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dp[35];

int rec(int n) {
    if (0 <= dp[n]) return dp[n];
    if (n == 0) return 1;
    int s1 = 0 <= (n - 1) ? rec(n - 1) : 0;
    int s2 = 0 <= (n - 2) ? rec(n - 2) : 0;
    int s3 = 0 <= (n - 3) ? rec(n - 3) : 0;
    dp[n] = s1 + s2 + s3;
    return dp[n];
}

void solve(int n) {
    for (int i = 0; i < 35; ++i) dp[i] = -1;
    int x = rec(n);
    int y = x / 3650;
    int m = x % 3650;
    cout << (y == 0 ? 1 : y + 1) << endl;
}

int main() {
    while(true) {
        int n;
        cin >> n;
        if (n == 0) break;
        solve(n);
    }
    return 0;
}



Measured memory_bytes: 3012
#include <stdio.h>
#include <string.h>

int main() {
  char s[101], p[101];
  int ans = 0, is, ip, endip;
  scanf("%s%s", s, p);
  for(is = 0; is < strlen(s) && !ans; ++is, endip = 0) for(ip = 0; ip < strlen(p) && !ans && !endip; ++ip) {
    if(s[(is + ip) % strlen(s)] != p[ip]) {
      endip = 1;
    } else if(ip == strlen(p) - 1) ans = 1;
  }
  printf("%s\n", ans ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 524
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
int t,n;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vvi in;
bool check(int a,int b){return a>=0&&b>=0&&a<n&&b<n;}
void f(int a,int b){
	in[a][b]^=1;
	rep(i,4){
		int nx=a+dx[i];
		int ny=b+dy[i];
		if(!check(nx,ny))continue;
		if(in[nx][ny]==t)f(nx,ny);
	}
}
int main(){
	int m;
	cin>>n>>m;
	in=vvi(n,vi(n));
	rep(i,n)rep(j,n)cin>>in[i][j];
	while(m--){
		int q;
		cin>>q;
		if(q==0){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			a--;b--;
			d/=90;
			while(d--){
				vvi tmp=in;
				rep(i,c)rep(j,c)tmp[i+a][j+b]=in[a+c-j-1][b+i];
				in=tmp;
			}
		}else if(q==1){
			int a,b,c;
			cin>>a>>b>>c;
			a--;b--;
			rep(i,c)rep(j,c)in[i+a][j+b]^=1;
		}else if(q==2){
			int a;
			cin>>a;
			a--;
			in[a].pb(in[a][0]);
			in[a].erase(in[a].begin());
		}else if(q==3){
			int a;cin>>a;a--;
			in[a].insert(in[a].begin(),in[a][n-1]);
			in[a].erase(in[a].end()-1);
		}else if(q==4){
			int a,b;
			cin>>a>>b;a--;b--;
			t=in[a][b];
			f(a,b);
		}
	}
	rep(i,n){cout<<in[i][0];rep(j,n-1)cout<<" "<<in[i][j+1];cout<<endl;}
}

Measured memory_bytes: 1236
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;

namespace AtCoder {
    class Program {
        static void Main(string[] args) {

            var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var a = input[0];
            var b = input[1];
            var t = input[2];

            int ans = (int)(t + 0.5) / a * b;
            Console.WriteLine(ans);
        }
    }
}


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

int main() {
  int K,N;
  cin >> K >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i=0;i<N;i++){
  cin >> A.at(i);
  if (i>=1){
  B.at(i-1)=A.at(i)-A.at(i-1);
  }
  }
  B.at(N-1) = K-A.at(N-1)+A.at(0);
  sort(B.begin(),B.end());
  cout << K - B.at(N-1) << endl;
}


Measured memory_bytes: 1920
#include<stdio.h>
int main(void)
{
	int i,n,m,h[25+1];
	scanf("%d",&n);
	while(n!=0) {
		for(i=0;i<n;i++) {
			scanf("%d",&h[i]);
		}
		m=32;
		while(m!=0) {
			for(i=0;i<n;i++) {
				if((m-(m-1%5))+0.5 < m) {
					m=m-((m-1)%5)+0.5;
					printf("%d\n",m);
				}
				else {
					m=0;
					printf("%d\n",m);
					break;
				}

				if((m-(m-1%5))+0.5 < m) {
					m=m-h[i];
					printf("%d\n",m);
				}
				else {
					m=0;
					printf("%d\n",m);
					break;
				}
			}
		}
	scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 600
/*
 * @Author: RBQRBQ
 * @Date: 2020-03-21 20:39:45
 * @LastEditors: RBQRBQ
 * @LastEditTime: 2020-03-22 17:33:32
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;ll f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        x=x*f;
    }
}
using namespace IO;
VI num;
int N;
bool judge(vector<int> a)
{
    for(auto p:a)
    {
        if(p==2) return false;
    }
    return true;
}
bool judge2(vector<int> a)
{
    for(auto p:a)
    {
        if(p==1) return false;
    }
    return true;
}
int main()
{
    //freopen("B.in","r",stdin);
    bool ok=true;
    read(N);
    for(int i=1;i<=N;i++)
    {
        char s;
        scanf("%c",&s);
        num.push_back((s-'0'));
    }
    VI res;
        for(int i=1;i<num.size();i++)
        {
            res.push_back(abs(num[i]-num[i-1]));
        }
    swap(res,num);
    if(num.size()==1)
    {
        cout<<num[0];
        return 0;
    }
    if(judge2(num))
    {
        ok=false;
        for(auto it=num.begin();it!=num.end();it++)
        (*it)=(*it)/2;
    }
    for(;;)
    {
        if(judge(num)||num.size()==1) break;
        VI res;
        for(int i=1;i<num.size();i++)
        {
            res.push_back(abs(num[i]-num[i-1]));
        }
        swap(res,num);

    }
    int j0=0,j1=0,o0=0,o1=0;
    N=num.size()-1;
    int q=-1;
    if(N==0)
    {
        cout<<num[0];
        return 0;
    }
    for(auto p:num)
    {
        q++;
        if(p==0)
        {

            if((N&q)==q) j0++;
            else o0++;
        }
        if(p==1)
        {
            if((N&q)==q) j1++;
            else o1++;
        }
    }
    if(j0%2==1&&j1%2==1)
    {
        if(ok) cout<<1;
        else cout<<2;
    }
    if(j0%2==0&&j1%2==1)
    {
        if(ok) cout<<1;
        else cout<<2;
    }
    if(j0%2==1&&j1%2==0)
    {
        cout<<0;
    }
    if(j0%2==0&&j1%2==0)
    {
        cout<<0;
    }
    
}

Measured memory_bytes: 16520
#include <cstdio>

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define FOR(i, l, r) for(LL i = (l)    ; i <  (r); i++)
#define REV(i, l, r) for(LL i = (r) - 1; i >= (l); i--)
#define INC(i, n) FOR(i, 0, n)
#define DEC(i, n) REV(i, 0, n)
#define INC1(i, n) FOR(i, 1, (n) + 1)
#define DEC1(i, n) REV(i, 1, (n) + 1)


LL n, x, a[2000];
LL min[2000][2000];

int main() {
	scanf("%lld%lld", &n, &x);
	INC(i, n) { scanf("%lld", &a[i]); }
	
	INC(i, n) {
	INC(j, n) {
		if(j == 0) { min[i][0] = a[i]; continue; }
		
		LL v = a[ (n + (i - j)) % n ];
		LL m = min[i][j - 1];
		min[i][j] = (v < m ? v : m);
	}
	}
	
	LL ans = 2000000000001;
	INC(j, n) {
		LL sum = 0;
		INC(i, n) { sum += min[i][j]; }
		sum += j * x;
		if(sum < ans) { ans = sum; }
	}
	
	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 31488
public class Hello {
    public static void Main(){
        // 1行に複数の入力値がある場合の例
        string [] inputs = System.Console.ReadLine().Split(' ');
        int a = int.Parse(inputs[0]);
        int b = int.Parse(inputs[1]);
        int c = (a * b);
        int d = (a + b) * 2;
        System.Console.WriteLine(c + " " + d);
    }
}


Measured memory_bytes: 9088
# -*- coding: utf-8 -*-

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"


################ DANGER ################
test = ""

########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  


def maximized(a):
    """
    1 -2 3 -4 5
    全探索より速い 
    """
    dp = [0] * (len(a) + 1)
    for i in range(len(a)):
        dp[i+1] = max(dp[i], dp[i] + a[i])
    return dp[-1]


def A_Frog1(a):
    """
    '''
    4
    10 30 40 20
    ans 30
    '''
    '''
    2
    10 10
    ans 0
    '''
    '''
    6
    30 10 60 10 60 50
    ans 40
    '''
    """
    n, h = len(a), a
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(1, n - 1):
        dp[i+1] = min(
                dp[i-1] + abs(h[i+1] - h[i-1]), 
                dp[i] + abs(h[i+1] - h[i]))
    return dp[-1]
    
    

if __name__ == "__main__":
    ################## IO ##################
    input2()
    a = list(map(int, input2().split()))
    print(A_Frog1(a))
    
    
    
    

Measured memory_bytes: 13784
#include <bits/stdc++.h>
#define int long long
#define N 100011

using namespace std;

int n, h[N], opt[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for(int i=0; i<n; i++) cin >> h[i];
	opt[n-1] = 0;
	for(int i=n-2; i>=0; i--) {
		opt[i] = abs(h[i] - h[i+1]) + opt[i+1];
		if(i < n-2) opt[i] = min(opt[i], abs(h[i] - h[i+2]) + opt[i+2]);
	}
	cout << opt[0] << endl;
	return 0;
}


Measured memory_bytes: 1792
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let x: usize = scan(tokens);
    let y: usize = scan(tokens);
    let z: usize = scan(tokens);
    println!("{} {} {}", z, x, y);
}


Measured memory_bytes: 4352
#include <stdio.h>
int F[44];

int fibonacci();

int main(){
    int index;
    scanf("%d", &index);
    fibonacci();
    printf("%d\n", F[index]);
    return 0;
}

int fibonacci()
{
    F[0] = 1;
    F[1] = 1;
    for (int i = 2; i < 45; ++i) F[i] = F[i-2] + F[i-1];
}


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> have(n,0);
  rep(i,0,k){
    int d;
    cin >> d;
    rep(j,0,d){
      int a;
      cin >> a;
      have[a-1]++;
    }
  }

  int ans = 0;

  rep(i,0,n){
    if(have[i]==0) ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	
	int k;
	cin>>k;
	int arr[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	bool dp[k+1];
	memset(dp,false,sizeof(dp));
	for(int i=0;i<=k;i++)
	{
		for(int j=0;j<n;j++)
		{
			   if(i-arr[j]>=0)
               {
		    	if(dp[i-arr[j]]==false)
                {
		    	   dp[i]=true;
		    	   break;
		    	}
		    }
			
		}	
	}
// 	for(int i=0;i<=k;i++)
// 	cout<<dp[i]<<" ";
	if(dp[k]==true)
		cout<<"First"<<endl;
	else
		cout<<"Second"<<endl;
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<uint32_t> A(N);
  uint32_t B=0;
  for(uint32_t &i:A){
    cin>>i;
    B^=i;
  }
  for(int i=0;i<N;i++){
    cout<<(A[i]^B);
    if(i==N-1)
      cout<<endl;
    else
      cout<<' ';
  }
}

Measured memory_bytes: 3932