akhauriyash/Code-Regression huggingface dataset:
/*
 *  Author  : StelaYuri
 * Language : GNU G++ 14
 */

//#pragma comment(linker,"/STACK:1024000000,1024000000")
//#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<functional>
#include<iomanip>
//#include<unordered_map>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define pb push_back
#define eb emplace_back
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const double angcst=PI/180.0;
const ll mod=1e9+7;
ll max_3(ll a,ll b,ll c){if(a>b&&a>c)return a;if(b>c)return b;return c;}
ll min_3(ll a,ll b,ll c){if(a<b&&a<c)return a;if(b<c)return b;return c;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}


void solve()
{
    vector<int> x,y;
    int a,b;
    int n;
    cin>>n;
    rep(i,1,n)
    {
        cin>>a>>b;
        x.pb(a-b);
        y.pb(a+b);
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    cout<<max(x[n-1]-x[0],y[n-1]-y[0])<<'\n';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 5124
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def main():
    N, M = [int(x) for x in input().split()]
    ret = "Yes" if N == M else "No"
    return ret


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

Measured memory_bytes: 23172
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll a,b,c;
  cin>>a>>b>>c;
  ll ans=min(a+b,b+c);
  ans=min(ans,a+c);
  cout<<ans<<endl;
}


Measured memory_bytes: 3608
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.*;

class Main
{
 public static void main(String[] args) throws IOException
 {
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     String str = br.readLine();
     String[] ab = str.split(" ", 0);
     int a = Integer.parseInt(ab[0]);
     int b = Integer.parseInt(ab[1]);

     if(a<b){
         System.out.println("a < b");
     }else if(a>b){
         System.out.println("a > b");
     }else if(a==b){
         System.out.println("a == b");
 
 
 }
}
}

Measured memory_bytes: 24232
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<P> vp;

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<string> s(n);
    rep(i,n){
        cin >> s[i];
    }
    rep(i,n){
        rep(j,m){
            if(s[i][j] == '.'){
                int val = 0;
                rep(k,8){
                    int u = i+dx[k],v = j+dy[k];
                    if(0 <= u && u < n && 0 <= v && v < m && s[u][v] == '#'){
                        val++;
                    }
                }
                s[i][j] = (char)(val+'0');
            }
        }
    }
    rep(i,n){
        rep(j,m){
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0]*N)
li = [[] for i in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    li[r].append((i, l-1))

now = 0
for r in range(1, N+1):
    for i, l in li[r]:
        while now < r:
            c = C[now]
            pre_idx, last_appeared[c] = last_appeared[c], now
            if pre_idx >= 0:
                st.update(pre_idx, 0)
            st.update(now, 1)
            now += 1
        ans[i] = st.query(l, r)


print(*ans, sep='\n')

Measured memory_bytes: 172668
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#define int long long
#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
#define MIN -(9223372036854775807 / 2)
#define INF 9223372036854775807 / 2
#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()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair


using namespace std;

std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }


signed main() {
	int A, B, C;
	cin >> A >> B >> C;
	/*
	bool f = false;
	if (A + B > C) f = true;
	if (B + C > A) f = true;
	if (C + A > B) f = true;
	*/
	bool f = false;
	if (A == B && B == C) f = true;
	if (f) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}

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

int main(){
	long long A,B,C;
	cin >> A >> B >> C;
	long long ans;
	if(A%2==0 || B%2==0 || C%2==0)ans=0;
	else{
		ans=A*B;
		ans=min(ans,A*C);
		ans=min(ans,B*C);
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int N, D, A;
    cin >> N >> D >> A;
    vector<int> X(N), H(N);
    vector<pair<int, int>> data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i].first >> data[i].second;
    }
    sort(data.begin(), data.end());
    for (int i = 0; i < N; i++) {
        tie(X[i], H[i]) = data[i];
    }
    
    int right = 0;
    vector<long long> damage(N+1, 0), cnt(N, 0);
    
    for (int left = 0; left < N; left++) {
        while (right < N && abs(X[left]-X[right]) <= 2*D) right++;
        H[left] -= damage[left];
        if (H[left] > 0) {
            int K = (H[left]+A-1)/A;
            damage[left] += K*A;
            damage[right] -= K*A;
            cnt[left] += K;
        }
        damage[left+1] += damage[left];
    }
    
    long long ans = 0;
    for (int i = 0; i < N; i++) ans += cnt[i];
    cout << ans << endl;
    return 0;
}

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

long long H, W, A[39][39], dp[999][39][39];

int main() {
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) cin >> A[i][j];
	}
	for (int i = 0; i < 999; i++) {
		for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++) dp[i][j][k] = (1 << 30); }
	}
	dp[0][1][1] = 0;
	for (int i = 0; i < 900; i++) {
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
				for (int l = 0; l < 4; l++) {
					int cx = j + dx[l], cy = k + dy[l];
					if (cx <= 0 || cy <= 0 || cx > H || cy > W) continue;
					dp[i + 1][cx][cy] = min(dp[i + 1][cx][cy], dp[i][j][k] + 1LL * (2 * i + 1) * A[cx][cy]);
				}
			}
		}
	}
	long long minx = (1LL << 60);
	for (int i = 0; i <= 900; i++) minx = min(minx, dp[i][H][W]);
	cout << minx << endl;
	return 0;
}


Measured memory_bytes: 14968
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/mman.h>

using namespace std;

#define forsn(i,s,n) for(int i = (s);i < (int)(n);i++)
#define forn(i,n) forsn(i,0,n)

typedef long long int tint;

int main() {
	tint n, a, b; cin >> n >> a >> b;
	
	tint dist = abs(a - b);
	
	if (dist % 2) {
		tint minToLeftBorder = min(a, b) + ((dist - 1) / 2);
		a = n - a + 1, b = n - b + 1;
		tint minToRightBorder = min(a, b) + ((dist - 1) / 2);
		
		cout << min(minToLeftBorder, minToRightBorder) << endl;
	} else {
		cout << dist / 2 << endl;
	}
}


Measured memory_bytes: 256
n, k, s = map(int, input().split())
A = [0]*n
for i in range(1, n+1):
    if i <= k:
        A[i-1] = s
    else:
        if s == 10**9:
          A[i-1] = 1
        else:
          A[i-1] = 10**9
print(*A)


Measured memory_bytes: 6684
#include <iostream>

using namespace std;

int main(){
  int n, l, r;

  while(1){
    cin >> n >> l >> r;
    if(n == 0 ) break;
    
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];

    int ansidx = -1, ans = 0;
    for(int x = l; x <= r; x++){
      for(int j = 0; j < n; j++){
        if( x % a[j] == 0 && x >= a[j]){
          ansidx = j;
          break;
        }
      }
      if(ansidx%2 == 0) ans++;
      if(ansidx == -1 && n % 2 == 0) ans++;
      ansidx = -1;
    }

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



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

int main(){
    int A[3][3];
    rep(i, 3) cin >> A[0][i];
    rep(i, 3) cin >> A[1][i];
    rep(i, 3) cin >> A[2][i]; 
    int N;
    cin >> N;
    int b[N];
    rep(i, N) cin >> b[i];

    int mark[3][3];
    rep(i, 3) rep(j, 3) mark[i][j] = 0;

    for(int k = 0; k < N; k++){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if (A[i][j] == b[k]){
                    mark[i][j] = 1;
                }
            }
        }
    }

    for(int i = 0; i < 3; i++){
        if ( (mark[i][0] == 1) && (mark[i][1] == 1) && (mark[i][2] == 1) ){
            cout << "Yes" << endl;
            return 0;
        }
    }

    for(int j = 0; j < 3; j++){
         if ( (mark[0][j] == 1) && (mark[1][j] == 1) && (mark[2][j] == 1) ){
            cout << "Yes" << endl;
            return 0;
        }
    }

     if ( (mark[0][0] == 1) && (mark[1][1] == 1) && (mark[2][2] == 1) ){
            cout << "Yes" << endl;
            return 0;
    }

      if ( (mark[0][2] == 1) && (mark[1][1] == 1) && (mark[2][0] == 1) ){
            cout << "Yes" << endl;
            return 0;
    }

    cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
k = int(input())
import math

l = [0 for i in range(k+1)]

for a in range(1, k+1):
    for b in range(1, k+1):
        l[math.gcd(a, b)-1] += 1

sum = 0
for i in range(1, k+1):
    for c in range(1, k+1):
        sum += l[i-1] * math.gcd(i, c)

print(sum)

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

int main(){
  int n, d, a;
  cin >> n >> d >> a;
  vector<int>x(n);
  vector<pair<int, int>>xh(n); //座標, HP
  for(int i=0; i<n; i++){
    cin >> xh[i].first >> xh[i].second;
    if(xh[i].second%a==0){ //A=1に正規化（？）
      xh[i].second/=a;
    }
    else{
      xh[i].second/=a;
      xh[i].second++;
    }
  }
  sort(xh.begin(), xh.end());
  for(int i=0; i<n; i++){
    x[i] = xh[i].first;
  }
  
  long ret = 0;
  
  vector<int>diff(n+1);
  diff[0]=xh[0].second;
  for(int i=1; i<n; i++){
    diff[i] = xh[i].second-xh[i-1].second;
  }
  diff[n]=0;
  int lefth = 0;
  for(int i=0; i<n; i++){
    lefth += diff[i];
    if(lefth>0){
      ret += lefth;
      diff[i]-=lefth;
      
      diff[upper_bound(x.begin(), x.end(), x[i]+2*d)-x.begin()]+=lefth;
      lefth=0;
    }
  }
  cout << ret;
  return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<iomanip>

using namespace std;

int main() {
	int a;
	cin >> a;
	int x[100];

	for (int i = 0; i < a; i++) {
		int tmp;
		cin >> tmp;
		x[i] = tmp;
	}

	long double ans = 0.0;

	for (int i = 0; i < a; i++) {
		ans += 1.0L / static_cast<long double>(x[i]);
	}

	cout << setprecision(15) << 1.0L / ans;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  long long n,a,b;
  cin >> n >> a >> b;
  long long sum = 0;
  sum = a + b;
  if( a == 0 )
  {
    cout << 0 << endl;
  }
  else if( b == 0 )
  {
    cout << n << endl;
  }
  else
  {
    if( n % sum <= a )
    {
      cout << a * (n / sum) + n % sum<< endl;
    }
    else
    {
      cout << a * (n / sum) + a<< endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
import math
import collections
def main():

    mod = pow(10, 9) + 7
    N = int(input())
    AB = []
    pos = collections.defaultdict(int)
    neg = collections.defaultdict(int)
    x = 0
    y = 0

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

    point = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A == 0 and B == 0:
            point += 1
        elif A == 0:
            y += 1
        elif B == 0:
            x += 1
        else:
            g = gcd(abs(A), abs(B))
            A = A // g
            B = B // g
            if A < 0:
                A, B = -A, -B
            if B > 0:
                pos[(A, B)] += 1
            else:
                neg[(A, B)] += 1


    pow2 = [1]
    for _ in range(1, N+1):
        pow2.append((pow2[-1] * 2) % mod)

    # print(pos)
    # print(neg)
    # print(x)
    # print(y)
    # print("----")

    v = 1
    if x > 0 and y > 0:
        v *= (pow2[x] + pow2[y] - 1)
    elif x > 0:
        v *= pow2[x]
    else:
        v *= pow2[y]
    v %= mod

    for z in pos:
        A, B = z
        w = (B, -A)
        if w not in neg:
            v *= pow2[pos[z]]
        else:
            v *= (pow2[pos[z]] + pow2[neg[w]] - 1)
        v %= mod
    # print("here", v)

    for w in neg:
        A, B = w
        z = (-B, A)
        if z not in pos:
            # print('ya', z)
            v *= pow2[neg[w]]
        v %= mod
    # print("there", v)

    return (v - 1 + point) % mod
if __name__ == '__main__':
    print(main())

Measured memory_bytes: 138564
h,w=map(int,input().split())
grid=[list(input())  for i in range(h)]
for i in range(w)[::-1]:
    a=[grid[j][i] for j in range(h)]
    if not "#" in a:
        for j in range(h):
            del grid[j][i]
for i in grid:
    if "#" in i:print(*i,sep="")
    

Measured memory_bytes: 4596
import java.util.*;

class Main {
    static int[] par; // 親の番号
    static int[] ws;  // 親との重みの差
    
    public static void WeightedUnionFind(int n){
        par = new int[n];
        ws  = new int[n];
        for(int i = 0; i < n; i++){ par[i] = -1; }
    }
    
    public static int find(int x){
        if(par[x] < 0){
            return x;
        }else{
            final int parent = find(par[x]);
            ws[x] += ws[par[x]];
            return par[x] = parent;
        }
    }
    
    public static int weight(int x){
        find(x); 
        return ws[x];
    }
    
    public static boolean union(int x, int y, int w){ // x <-(w)- y (x + w = y)
        w += weight(x); 
        w -= weight(y);
        x = find(x); y = find(y);
        
        if(x != y){
            if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
                int tmp = x; x = y; y = tmp; w = -w;
            }
            par[x] += par[y]; par[y] = x;
            ws[y] = w;
            return true;
        }else{
            return false;
        }
    }
    
    public static boolean same(int x, int y){
        return find(x) == find(y);
    }
    
    public static Integer diff(int x, int y){ // x - y を求める. 比較不能ならnull.
        if(!same(x, y)){ return null; }
        return weight(x) - weight(y);
    }
    // size()はUnionFindと同じなので省略.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        WeightedUnionFind(n);
        for (int i=0;i<q;i++) {
            int flag = sc.nextInt();
            if (flag==0) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int z = sc.nextInt();
                union(x, y, z);
            } else {
                int x = sc.nextInt();
                int y = sc.nextInt();
                Integer ans = diff(y, x);
                if (ans==null) {
                    System.out.println("?");
                } else {
                    System.out.println(ans);
                }
            }
        }
    }
}


Measured memory_bytes: 175196
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
  
public class Main{
  
  public static void main(String [] args)throws IOException{
      
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int [] num = new int[51];
    for(int a = 0; a <= 9; a++)
      for(int b = 0; b <= 9; b++)
        for(int c = 0; c <= 9; c++)
          for(int d = 0; d <= 9; d++) 
             num[a+b+c+d]++;
    String ln ="";
    while((ln = br.readLine())!= null)
      System.out.println(num[Integer.parseInt(ln)]);    
         
      
    }
      
}  
 

 

Measured memory_bytes: 24236
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[[0]*3 for _  in range(n)]
dp[0]=[a[0][0],a[0][1],a[0][2]]
for i in range(n-1):
    for j in range(3):
        for k in range(3):
            if j!=k:
                dp[i+1][j]=max(dp[i+1][j],dp[i][k] + a[i+1][j])
print(max(dp[n-1]))


    


Measured memory_bytes: 75224
import java.util.*;
public class Main{
    public static void main (String args[]){

        //初期処理
        Scanner sc=new Scanner(System.in);
        int answer=0;
        int N= sc.nextInt();
        int A= sc.nextInt();
        int B= sc.nextInt();
        
        int trainFee=N*A;
        int taxiFee=B;
        if(trainFee>=taxiFee){
            answer=taxiFee;
        }
        if(trainFee<taxiFee){
            answer=trainFee;
        }
        System.out.println(answer);
    }
}

Measured memory_bytes: 23764
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  char map[1010][1010];
  for (int i = 0; i <= w + 1; i++) {
    map[0][i] = '#';
  }
  for (int i = 1; i <= h; i++) {
    map[i][0] = '#';
    for (int j = 1; j <= w; j++) {
      cin >> map[i][j];
    }
    map[i][w + 1] = '#';
  }
  for (int i = 0; i <= w + 1; i++) {
    map[h + 1][i] = '#';
  }
  int64_t dp[1001][1001] = {};
  dp[1][1]               = 1;
  const int64_t MOD      = std::pow(10, 9) + 7;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      dp[i][j] += (map[i][j - 1] == '.') ? dp[i][j - 1] : 0;
      dp[i][j] += (map[i - 1][j] == '.') ? dp[i - 1][j] : 0;
      dp[i][j] %= MOD;
    }
  }
  cout << dp[h][w] << endl;

  return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

using namespace std;

int main(){

    int n,a,b;
    cin >> n >> a >> b;

    cout << min(n * a, b) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  while (1){
    int n, l;
    cin >> n >> l;
    if (n == 0 && l == 0){
      break;
    }
    vector<char> d(n);
    vector<int> p(n);
    for (int i = 0; i < n; i++){
      cin >> d[i] >> p[i];
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++){
      a[i] = i + 1;
    }
    int t = 0;
    vector<int> ans;
    while (1){
      t++;
      for (int i = 0; i < n; i++){
        if (d[i] == 'L'){
          p[i]--;
        }
        if (d[i] == 'R'){
          p[i]++;
        }
      }
      for (int i = 0; i < n - 1; i++){
        if (p[i] > p[i + 1]){
          swap(p[i], p[i + 1]);
          swap(d[i], d[i + 1]);
          swap(a[i], a[i + 1]);
        }
      }
      for (int i = 0; i < n - 1; i++){
        if (p[i] == p[i + 1] && d[i] == 'R' && d[i + 1] == 'L'){
          swap(d[i], d[i + 1]);
        }
      }
      for (int i = 0; i < n; i++){
        if (p[i] == l){
          ans.push_back(a[i]);
        }
      }
      for (int i = 0; i < n; i++){
        if (p[i] == 0){
          ans.push_back(a[i]);
        }
      }
      if (ans.size() == n){
        break;
      }
    }
    cout << t << ' ' << ans[n - 1] << endl;
  }
}


Measured memory_bytes: 3116
while True:
    cards = map(int, raw_input().split())
    if cards == [0]:
        break

    ace = 0
    sum = 0
    for i in cards:
        if i > 10:
            sum += 10
        else:
            sum += i
            if i == 1:
                ace += 1

    for i in range(ace):
        if sum + 10 <= 21:
            sum += 10

    print sum if sum <= 21 else 0

Measured memory_bytes: 4224
n, m = gets.to_i, gets.to_i

s = m

n.times do
  in_car, out_car = gets.split.map(&:to_i)
  
  m += in_car - out_car
  
  if m < 0
    s = 0
    break
  else
    s = [s, m].max
  end
end

puts s

Measured memory_bytes: 8784
/*Arnab's Code
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(n) push_back(n)
#define mp(a,b) make_pair(a,b)
#define vll vector<ll>
#define vii vector<int>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define take(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define takes(a,n,st) for(ll i=st;i<n+st;i++)cin>>a[i]
ll sum(ll a[],ll n,ll s){ for(ll i=0;i<n;i++)s+=a[i]; return s;}
#define mod 1000000009
ll power(ll x, ll y, ll p)  {  
    ll res = 1;  
    x = x % p;   
    if (x == 0) return 0;  
    while (y > 0){  
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}
char s[117];
void solve(){
	ll k,i,l;
	cin>>k;
	cin>>s;
	l=strlen(s);
	for(i=0;i<min(k,l);i++)
		cout<<s[i];
	if(strlen(s)>k)
		cout<<"...";
	return;
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ll t,T;
//	cin>>T;
	T=1;
	for(t=1;t<=T;t++){
//		cout<<"Case #"<<t<<": ";
		solve();
	}
	return 0;
}

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

class dice_class:
    def __init__(self, list):
        self.num = list

    def sut(self, top):  #set_up_top
        i = 0
        while i < 3:
            if self.num[0] == top:
                break
            else:
                self.roll('E')
            if self.num[0] == top:
                break
            else:
                self.roll('N')
            i += 1

    def suf(self, front):   #set_up_front
        i = 0
        while i < 4:
            if self.num[1] == front:
                break
            else:
                self.roll('SEN')
            i += 1

    def roll(self, s):
        for i in s:
            if i == 'E':
                self.rollE()
            elif i == 'N':
                self.rollN()
            elif i == 'S':
                self.rollS()
            elif i == 'W':
                self.rollW()

    def rollE(self):
        self.num = [self.num[3], self.num[1], self.num[0], self.num[5], self.num[4], self.num[2]]

    def rollN(self):
        self.num = [self.num[1], self.num[5], self.num[2], self.num[3], self.num[0], self.num[4]]

    def rollS(self):
        self.num = [self.num[4], self.num[0], self.num[2], self.num[3], self.num[5], self.num[1]]

    def rollW(self):
        self.num = [self.num[2], self.num[1], self.num[5], self.num[0], self.num[4], self.num[3]]


if __name__ == "__main__":
    n = int(raw_input())
    dice_List = []
    for i in range(n):
        dice_List.append(dice_class(map(int, raw_input().split())))
    flg = True

    for i in range(n):
        for j in range(i+1, n):
            for k in range(6):
                if k % 2:
                    dice_List[i].roll('E')
                else:
                    dice_List[i].roll('N')
                dice_List[j].sut(dice_List[i].num[0])
                dice_List[j].suf(dice_List[i].num[1])
                if dice_List[i].num == dice_List[j].num:
                    flg = False
                    break
    if flg:
        print "Yes"
    else:
        print "No"

Measured memory_bytes: 6500
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long 
const int N=2e5+5;
int h,n;
vector<int>v;
int32_t main(){
	IOS;
	
	//code

	cin>>h>>n;
	v.resize(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
		if(i!=0)
			v[i]+=v[i-1];
	}

	if(v[n-1]>=h){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	//code
	
	return 0;

}

Measured memory_bytes: 1024
#include <cstdio>

void insertionSort(int *a, int N){
	int i,j,k,v;
	for (i=1; i<N; i++){
		for (k=0; k<N-1; k++){
			std::printf("%d ", a[k]);
		}
		std::printf("%d\n", a[N-1]);
		v = a[i];
		j=i-1;
		while(j>=0 && a[j]>v){
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = v;
	}
	for (k=0; k<N-1; k++){
		std::printf("%d ", a[k]);
	}
	std::printf("%d\n", a[N-1]);
}

int main(){
	int N, i;
	int *a;
	std::scanf("%d", &N);
	a = new int[N];
	i = 0;
	for (i=0; i<N; i++){
		std::scanf("%d", &a[i]);
	}
	insertionSort(a, N);
	return 0;
}

Measured memory_bytes: 2756
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

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

  int N;
  cin >> N;
  vector<int> A(N);
  multiset<int> st;
  repr(i, N, 0) {
    cin >> A[i];
  }

  for (int i = N-1; i >= 0; --i) {
    auto it = st.upper_bound(A[i]);
    if (it == st.end()) {
      st.insert(A[i]);
    } else {
      st.erase(it);
      st.insert(A[i]);
    }
  }
  cout << st.size() << endl;
}

Measured memory_bytes: 8324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
//stoi(s) : string→int stoll(s) :string→longlong
const double PI=3.14159265358979323846;

struct place{
    double x;
    double y;
};

double dis(place a,place b){
    double dx = abs(a.x - b.x);
    double dy = abs(a.y - b.y);
    double s2 = pow(dx,2.0) + pow(dy,2.0);
    double s1 = pow(s2,0.5);
    return s1;
}

int main(){
    double a,b,h,w;
    cin >> a >> b >> h >> w;
    place L,S;
    double W = 6*w;
    W = W*PI/180;
    L.x = a*cos(-W); //L 分針
    L.y = a*sin(-W);
    double p = 30.0*h + 0.5*w;
    p = p*PI/180;
    S.x = b*cos(-p);
    S.y = b*sin(-p); 

  
    cout << fixed << setprecision(14) << dis(L,S) << endl;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

int main() {
    int n;
    cin >> n;
    list<int> b;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        b.push_back(temp);
    }
    stack<int> ans;
    bool flag = true;
    for (int i = 0; i < n; i++) {
        // b[i]=iなるiで最大のやつを見つけたい(そのイテラをtargetとする)
        auto target = b.end();
        int now = 1;
        for (auto itr = b.begin(); itr != b.end(); itr++) {
            if (*itr == now) {
                target = itr;
            }
            now++;
        }
        if (target != b.end()) {
            ans.push(*target);
            b.erase(target);
        } else {
            flag = false;
            break;
        }
    }
    if (flag) {
        while (!ans.empty()) {
            cout << ans.top() << endl;
            ans.pop();
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}

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

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

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


vector<int> A, sum;
int N, M;

int check2(int num, int x, int m){
	if(m <= 0) return true;
	if(m > N) return false;
	// cout<<A[num]+A[m-1]<<" < "<<x<<endl<<endl;
	if(A[num] + A[m-1] <= x) return true;
	
	return false;
}

int count3(int num, int x){
	int l = 0, h = N+2, m;
	
	while(l + 1 < h){
		m = (l + h) / 2;
		
		if(check2(num, x, m)) {
			l = m;
		} else {
			h = m;
		}
	}
	// for(int i = 0; i <= N; i++){
		// cout<<"i = "<<i<<" check2 "<<check2(num,x,i)<<endl;
		// cout<<A[num]+A[i-1]<<" < "<<x<<endl<<endl;
	// }
	// cout<<"num = "<<num<<" x = "<<x<<" l = "<<l<<endl;
	
	// cout<<"res "<<A[num] * (N - l) + sum[l]<<" A "<<A[num]<<" "<<sum[l]<<endl;
	
	if(l < N) return A[num] * (N - l) + sum[l];
	else return 0;
}

int check(int num, int x, int m){ //cout<<"A"<<" num "<<num<<" m "<<m<<" x "<<x<<endl;
	if(m <= 0) return true;
	if(m > N) return false;
	
	if(A[x] + A[m-1] <= num) return true;
	
	return false;
}

int count2(int num, int x){
	int l = 0, h = N+1, m;
	
	while(l + 1 < h){
		m = (l + h) / 2;
		
		if(check(num, x, m)) {
			l = m;
		} else {
			h = m;
		}
	}
	
	return l;
}

int count(int num){
	int sum = 0;
	for(int i = 0; i < N; i++){
		sum += count2(num, i);
	}
	
	return sum;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	const int MAX = 110000;
	const int MAX2 = MAX * 2;
	
	int ans = 0, hoge = 0;
	
	cin>>N>>M;
	
	A.resize(N);
	sum.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>A[i];
	}
	
	sort(A.begin(), A.end());
	
	
	// for(int i = 0; i < N; i++){
		// for(int j = 0; j < N; j++){
			// cout<<A[i] + A[j]<<" ";
		// }
		// cout<<endl;
	// }
	// for(int i = 0; i < N; i++){
		// for(int j = 0; j < N; j++){
			// cout<<A[i] + A[j]<<" "<<count(A[i]+A[j])<<"   ";
		// }
		// cout<<endl;
	// }
	
	// cout<<"M = "<<M<<endl;
	int l = 0, h = MAX2, m;
	
	while(l + 1 < h){
		m = (l + h)>>1;
		// cout<<"<> "<<l<<endl;
		if(N * N - count(m) < M) {
			h = m;
		} else {
			l = m;
		}
	}
	sum = A;
	
	hoge = N * N - count(l);
	
	
	// cout<<"l = "<<l<<" hoge "<<hoge<<" h = "<<h<<endl;
	
	ans = (M - hoge) * (l+1);
	
	for(int i = N-2; i >= 0; i--){
		sum[i] += sum[i+1];
	}
	
	sum.push_back(0);
	
	for(int i = 0; i < N; i++){
		// cout<<"ans "<<ans<<endl;
		ans += count3(i, l);
	}
	
	// for(int i = 0; i < N; i++){
		// cout<<"i = "<<i<<" sum "<<sum[i]<<endl;
	// }
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 2688
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    string a = "AKIHABARA";
    size_t ia = 0, is = 0;
    while(1){
        bool change = false;
        while(ia < a.size() && is < s.size() && a[ia] == s[is]){
            ia++;
            is++;
            change = true;
        }
        if(ia < a.size() && a[ia] == 'A'){
            ia++;
            change = true;
        }
        if(!change){ break; }
    }
    cout << (ia == a.size() && is == s.size() ? "YES" : "NO") << '\n';
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
s = input()
t = input()
if s == t:
    print(n)
    exit()
cnt = 0
for i in range(n):
    suf = s[-i-1:]
    pre = t[:i+1]
    #print(suf,pre)
    if s[-i-1:] == t[:i+1]:
        cnt = len(pre)
print(n + n - cnt)


Measured memory_bytes: 10352
include Math
require 'bigdecimal'
def calc_area(a, b, sin_c)
  s = a * b * sin_c * 0.5
  return s #????§???????
end

def calc_length(a, b, cos_c)
  c = (a**2 + b**2 - 2*a*b*cos_c)**0.5
  l = a + b + c
  return l #????§???????
end

def calc_height(a, b, sin_c)
  h = b * sin_c
  return h #?????????a
end

input_values = gets.chomp.split.map(&:to_i)
a = input_values[0]
b = input_values[1]
c = input_values[2]
if c == 90 || c == 270
  sin_c = 1
  cos_c = 0
elsif c == 180 || c == 0
  sin_c = 0
  cos_c = 1
else
  c = (c / 180.0 * Math::PI)
  sin_c = BigDecimal(sin(c).to_s).floor(8).to_f
  cos_c = BigDecimal(cos(c).to_s).floor(8).to_f
end
puts calc_area(a, b, sin_c)
puts calc_length(a, b, cos_c)
puts calc_height(a, b, sin_c)

Measured memory_bytes: 8996
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(int i=a,__=b;i<=__;++i)
#define rep(i,a,b) for(int i=a,__=b;i<__;++i)
#define fd(i,a,b) for(int i=a,__=b;i>=__;--i)
#define ll long long
#define mo 1000000007

using namespace std;

int c[26],n;

int main(){
	scanf("%d\n",&n);
	int ans=1;
	for(int i=1;i<=n;++i)++c[getchar()-'a'];
	for(int i=0;i<26;++i)ans=1ll*ans*(c[i]+1)%mo;
	printf("%d",(ans+mo-1)%mo);
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

//順列を入力し、条件を満たす数を計算するクラス
class DividetheProblems{
    vector<int> *vec; //入力された数列を格納する配列
    int answer; //整数Kの選び方の数
    void func0(); //変数answerを求める関数
public:
    DividetheProblems(vector<int> *vec0);
    void print(); //変数answerを出力
};

DividetheProblems::DividetheProblems(vector<int> *vec0) {
    vec = vec0; //引数の配列をメンバ変数に格納
    func0(); 
}

//変数answerを求める関数
void DividetheProblems::func0(){
    sort(vec->begin(),vec->end()); //配列の値を昇順で並べ替え
    int centerIndex = vec->size() / 2; //配列の中心右のインデックスを求める
    answer = (*vec)[centerIndex] - (*vec)[centerIndex - 1]; //中心の2つの整数の差が答え 
}

void DividetheProblems::print(){
    cout << answer << endl;
}

int main(void){
    int N = 0;
    vector<int> vec;
    cin >> N; //配列の要素数を決定
    //配列の要素を入力
    vec.reserve(N + 1);
    for(int i = 0; i < N; i++){
        int value;
        cin >> value;
        vec.push_back(value);
    }
    DividetheProblems dp(&vec);
    dp.print();
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int x;
	cin >> x;
	int ans = 0;
	ans += (x / 500) * 1000;
	x %= 500;
	ans += (x / 5) * 5;
	cout << ans << endl;
}

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

#define int long long
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define printarr(arr, n) for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl;
#define pii pair<int,int>
#define mp(x, y) make_pair(x, y)
#define debug(x) cout << "#debug " << x << endl;
#define print2D(arr, n) cout << "\n_____________________\n";  for(int i = 1; i  <= n; i++){	for(int j = 1; j <= n; j++){cout << arr[i][j] << " ";}cout << endl;}cout << "\n_____________________\n";
#define mii map<int,int>
#define printmap(mm) for(map<int,int>::iterator itr = mm.begin(); itr!=mm.end(); itr++) cout << itr->first << "->" << itr->second << " "; cout << endl;
#define iterm(mm) for(map<int,int>::iterator itr = mm.begin(); itr!=mm.end(); itr++)
#define NO cout << "NO"; return 0;
#define MO 1000000007
#define N 500100
#define MX 2000000000

void preprocess(){
	
}

signed main(){
	FAST_IO;
	#ifndef ONLINE_JUDGE
	//freopen("/home/divakar/programs/input.txt","r",stdin);
	//freopen("/home/divakar/programs/output.txt","w",stdout);
	#endif
	clock_t clk = clock();

	preprocess();
	int t=1;
	//cout << " dsf ";
	//cin >> t; 
	while(t--){

		int n,k;
		cin >> n >> k;
		int arr[n];
		for (int i = 0; i < n; ++i)
		{
			cin >> arr[i];
		}

		int dp[n];
		dp[0] = 0;
		dp[1] = abs(arr[0]-arr[1]);

		for (int i = 2; i < n; ++i)
		{
			dp[i]=INT_MAX;
			for(int j = i-1; j >= 0 && i-j <= k; j--)
			{
				dp[i]=min(dp[j] + abs(arr[i]-arr[j]), dp[i]);
				//cout << "df";
			}

		}
		cout << dp[n-1] << endl;




        
		//cout << "ENDOFTEST "<< t << "\n";
	}









	// #ifndef ONLINE_JUDGE
	// clk = clock() - clk;
	// cout << "Time Elapsed: " << fixed << setprecision(10) << ((long double)clk)/CLOCKS_PER_SEC << "\n";
	// #endif
	return 0;
}






















Measured memory_bytes: 1792
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=5e18;
typedef pair<int,int> P;
signed main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,a[21][21]={};
  scanf("%d",&n);
  ll dp[1<<n]={};
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int i=0; i<(1<<n); i++) {
    int cnt=__builtin_popcount(i);
    for(int j=0; j<n; j++) {
      if((i&(1<<j))&&a[cnt-1][j]) {
        (dp[i]+=dp[i^(1<<j)])%=MOD;
      }
    }
  }
  printf("%d",dp[(1<<n)-1]);
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const ll INF = 1e14;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;

ll N,X;
ll lv[60];
ll P[60];

ll f(ll a,ll b) {
    if(a == 0) {
        if(b <= 0) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else if(b <= 1 + lv[a - 1]) {
        return f(a - 1,b - 1);
    }
    else {
        return P[a - 1] + 1 + f(a - 1,b - 2 - lv[a - 1]);
    }
}

int main() {
    cin >> N >> X;
    lv[0] = 1;
    P[0] = 1;
    for(int i = 1;i <= N;i++) {
        lv[i] = 3 + lv[i - 1] * 2;
        P[i] = 1 + P[i - 1] * 2;
    }
    cout << f(N,X) << endl;
}

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

namespace Contest
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(new int[] { 0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,3,3,3,3,8,8,11,11,11,11,14,14,32,32,35,35,35,35,42,42,42,42,49,49,49,49,49,49,75,75,86,86,86,86,86,86,123,123,131,131,131,131,148,148,153,153,170,170,170,170,170,170,227,227,227,227,227,227,250,250,323,323,324,324,324,324,354,354,354,354,384,384,384,384,384,391,491,491,529,529,529,529,529,529,543}[Convert.ToInt32(Console.ReadLine())]);
        }
    }
}


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

int main(){
    int m;
    int a[m];
    for (int i = 0; i < 3; i++) {
        cin >> a[i];
    }
    cout << a[2] << " " << a[0] << " " << a[1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

string s, t;
int main() {
  cin >> s >> t;
  i64 ans = 0;
  for (int i = 0; i < 3; ++i) if (s[i] == t[i]) ++ans;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main (void){
  int n,k,d[100],a,i,j,aa[100],ans=0;
  a=0;
  for(i=0;i<100;i++){aa[i]=0;}
  
  scanf("%d%d",&n,&k);
  
  for(i=0;i<k;i++){
    scanf("%d",&d[i]);
    
    for(j=0;j<d[i];j++){
      scanf("%d",&a);
      aa[a-1]=1;
    }  
  }  
  
  for(i=0;i<n;i++){
    if(aa[i]==0){ans++;}}
  printf("%d\n",ans);
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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(){
    cin.tie(0);
   	ios::sync_with_stdio(false);

    int N;
    cin >> N;
    map<string, int> ms;
    string tmp;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        ms[tmp]++;
    }

    int M;
    cin >> M;
    map<string, int> mt;
    for(int i = 0; i < M; i++){
        cin >> tmp;
        mt[tmp]++;
    }

    int ans = 0;
    for(auto itr = ms.begin(); itr != ms.end(); itr++){
        // cout << mt[itr->first] << endl;
        // cout << mt.find(itr->second) << endl;
        chmax(ans, itr->second - mt[itr->first]);
    }

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



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


int main(){
    int n,limit,ans;cin >> n >> limit;
    int l = 0;
    vector<int> cost(n);
    vector<int> sec(n);
    vector<int> compare(n);


    for(int i=0;i<n;i++){
        cin >> cost[i] >> sec[i];
    }
    for(int j=0;j<n;j++){
        if(sec[j]<=limit){
            compare[l] = cost[j];
            l = l + 1;
        }else{
            continue;
        }
    }

    
    if(l == 0){
        cout << "TLE" << endl;
    }else if(l == 1){
        cout << compare[0] << endl;
    }else if(l == 2){
        ans = min(compare[0],compare[1]);
        cout << ans << endl;
    }else{
        ans = min(compare[0],compare[1]);
        for(int m=2;m<l;m++){
            ans = min(ans,compare[m]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T & a, const T & b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7;

lint cnt = 0, N;
string s;
int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> s;
	N = SZ(s);
	lint s_cnt = 0;
	REP(i, N) {
		if (s[i] == 'S') s_cnt++;
		if (s[i] == 'T' && s_cnt > 0) {
			s_cnt--;
			cnt++;
		}
	}
	cout << N - cnt * 2 << endl;
}


Measured memory_bytes: 720