akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


int main(){
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r(R);
    for (int i = 0; i < R; i++) cin >> r[i];
    vector<vector<int>> dist(N+1, vector<int>(N+1, 100000000));
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N-1; i++) {
            for(int j = 2; j <= N; j++) {
                int d = dist[i][k] + dist[k][j];
                if (d < dist[i][j]) {
                    dist[i][j] = d;
                    dist[j][i] = d;
                }
            }
        }
    }
    
    vector<int> num(R);
    iota(num.begin(), num.end(), 0);
    int ans = -1;
    while(true) {
        int cand = 0;
        for (int i = 1; i < R; i++) {
            cand += dist[r[num[i]]][r[num[i-1]]];
        }
        if (ans < 0) ans = cand;
        else ans = min(ans, cand);
        if (!next_permutation(num.begin(), num.end())) break;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
import bisect


if __name__ == '__main__':
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            ans += bisect.bisect_left(L, L[i]+L[j])-j-1
    print(ans)


Measured memory_bytes: 3188
import itertools
import bisect
n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

*per, = itertools.permutations(range(1, n+1))

a = bisect.bisect_right(per, p)
b = bisect.bisect_right(per, q)

print(abs(a-b))


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int A ,B;
    cin >> A >> B;
    if(A>B){
        cout << 2*A-1 << endl;
    }else if(A<B){
        cout << 2*B-1 << endl;
    }else if(A==B){
        cout << A+B << endl;
    }

    return 0;
}

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


def main():
    n = int(input())
    lunlun = [[] for i in range(11)]
    lunlun[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 9
    if n < 10:
        print(n)
        exit()
    for j in range(0, 10):
        for a in lunlun[j]:
            for b in range(10):
                if abs((a % 10) - b) < 2:
                    lunlun[j + 1].append(10 * a + b)
                    cnt += 1
                    if cnt == n:
                        print(10 * a + b)
                        exit()

if __name__ == '__main__':
    main()


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

ll A;
double B;

int main() {
    cin >> A >> B;
    ll new_B = round(B * 100);
    cout << (A * new_B) / 100 << endl;
    return 0; 
}

Measured memory_bytes: 3740
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static StreamWriter sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
        static void Main(string[] args)
        {
            try
            {
                SetOut(sw);
                Solve.Answer();
                Out.Flush();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var n = IO.RInt;
            var a = IO.RSInt;

            int minNum;

            while (a.Length > 1)
            {
                Array.Sort(a);
                minNum = a[0];
                for (int i = 1; i < a.Length; i++)
                {
                    a[i] %= minNum;
                }
                a = a.Where(x => x != 0).ToArray();
            }
            WriteLine(a[0]);
        }
    }

    public class IO
    {
        #region Input
        public static int RInt => int.Parse(ReadLine());
        public static long RLong => long.Parse(ReadLine());
        public static double RDouble => double.Parse(ReadLine());

        public static string[] RSString => ReadLine().Split();
        public static int[] RSInt => ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        public static long[] RSLong => ReadLine().Split().Select(s => long.Parse(s)).ToArray();
        public static double[] RSDouble => ReadLine().Split().Select(s => double.Parse(s)).ToArray();
        #endregion

        #region Output
        public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
        public static void WriteLineYes_or_No(bool flag) => WriteLine(flag ? "Yes" : "No");
        public static void WriteLineYES_or_NO(bool flag) => WriteLine(flag ? "YES" : "NO");
        #endregion
    }

    public class Mod
    {
        #region
        private readonly static long M = 1000000007;

        public static long Add(long a, long b) => (a * b) % M;
        public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
        public static long Multi(long a, long b) => (a * b) % M;
        #endregion
    }
}

Measured memory_bytes: 23136
#include<bits/stdc++.h>
using namespace std;
int main()
{
    // 1st,3th,5th,7th,,,,,,,,,,,,,,,,,,,,,,,,,,,check,,,,,,,,R|| D||U
    // 2nd,4th,6th,.,,,,,,,,,,,,,,,,,,check  ....... L||D||U
    string s;
    cin>>s;
    int cnt=0,cn=0;
    for(int i=0; i<s.size(); i++)
    {
        if(i%2==0)
        {
            if(s[i]=='R'||s[i]=='D'||s[i]=='U')
                cnt++;
        }
        else
        {
            if(s[i]=='L'||s[i]=='D'||s[i]=='U')
                cn++;

        }
    }
    (cnt+cn == s.size())?cout<<"Yes":cout<<"No";

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n;
    cin>>n;
    long int arr[n],dp[n];
    for(long int i=0;i<n;i++)
    cin>>arr[i];
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(long int i=2;i<n;i++)
    {
        dp[i] = min((dp[i-1]+abs(arr[i]-arr[i-1])),(dp[i-2]+abs(arr[i]-arr[i-2])));
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 1792
function main(input) {
    const number = Number(input.split("\n")[0]);
    const numbers = Array.from({length:number} ,(v, i) => { return(i+1) });
    const result = numbers.reduce((acc, cur) => acc += cur);
    console.log(result);
}

// let input = "3";
// main(input);
main(require("fs").readFileSync("/dev/stdin","utf8"));
  

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

int main()
{
    int count[4][3][10] = {};
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        count[a - 1][b - 1][c - 1] += d;
    }
    for(int j = 0; j < 4; j++)
    {
        for(int l = 0; l < 3; l++)
        {
            for(int k = 0; k < 10; k++)
                cout << " " << count[j][l][k];
            cout << endl;
        }
      	if(j != 3)
        	cout << "####################" << endl;
    }
}


Measured memory_bytes: 3068
# 符号の数について、-が偶数だった場合、全てを打ち消せる
# 奇数だった場合、どれか一つが残る。
# `..,+,-,+,..`を→移動←移動できるので

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ret = sum(abs(a) for a in A)
    num_neg = sum(a < 0 for a in A)
    min_abs_A = min(abs(a) for a in A)
    if num_neg % 2 == 1:
        ret -= 2*min_abs_A
        
    print(ret)
    
solve()

Measured memory_bytes: 20004
#include <iostream>
using namespace std;
int main() 
{
	long n,l[88],i;
	cin >> n;
	l[0]=2;
	l[1]=1;

	for(i=2;i<=n;i++){
		l[i] = l[i-1]+l[i-2];
	} 
	cout << l[n] << endl;
	return 0;
}

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

int main() {

    int n, k, a[200000];
    vector< int > val(200001, 0);

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

    int sum = 0, cnt = 0;

    sort(val.begin(), val.end());
    for(auto p: val) {
        if(val.size() - cnt <= k) break;
        sum += p;
        cnt++;
    }

    cout << sum << endl;

}


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int INF = -10000;
    int X,Y,Z,K;
    cin>>X>>Y>>Z>>K;
    vector<long long> A(X),B(Y),C(Z);
    for(int i=0;i<X;i++)cin>>A[i];
    for(int i=0;i<Y;i++)cin>>B[i];
    for(int i=0;i<Z;i++)cin>>C[i];
    A.push_back(INF);
    B.push_back(INF);
    C.push_back(INF);

    sort(A.rbegin(),A.rend());
    sort(B.rbegin(),B.rend());
    sort(C.rbegin(),C.rend());

    priority_queue<pair<long long,long long>> pq;
    pq.emplace(A[0]+B[0]+C[0],0);

    unordered_set<int> seen;

    while(K>0) {
        long long sum = pq.top().first;
        long long key = pq.top().second;
        pq.pop();
        if(seen.find(key)!=seen.end())continue;
        cout<<sum<<endl;
        K--;
        seen.insert(key);
        int ki=key/(1000*1000);
        int kj=(key/1000)%1000;
        int kk=key%1000;

        pq.emplace(A[ki+1]+B[kj]+C[kk],key+1000*1000);
        pq.emplace(A[ki]+B[kj+1]+C[kk],key+1000);
        pq.emplace(A[ki]+B[kj]+C[kk+1],key+1);
    }
    
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
LL Z;
LL B[114514];
LL L[114514];
LL U[114514];
LL imos[114514];
vector<pll> es;

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> N >> Z;

  LL target = 0;
  rep(i, N) {
    cin >> B[i] >> L[i] >> U[i];
    target += B[i] * L[i];
    es.eb(pll(U[i]*(Z-B[i]) + B[i]*L[i], i));
  }
  sort(all(es), greater<pll>());
  imos[0] = es[0].X;
  reps(i, 1, N) {
    imos[i] = imos[i-1] + es[i].X;
  } 

  LL ans = 1LL << 61;
  rep(i, N) {
    int low = -1;
    int high = N;
    while (high - low > 1) {
      int mid = (high+low)/2;
      LL v = imos[mid];
      if (mid >= i) v -= es[i].X;
      if (target-v <= es[i].X) high = mid;
      else low = mid;
    }

    LL cnt = high+1;
    LL tot = imos[high];
    if (high >= i) {
      tot -= es[i].X;
      cnt--;
    }

    LL rem = target-tot;
    assert(rem <= es[i].X);
    LL sc = 0;
    int idx = es[i].Y;
    if (rem >= 0) {
      if (B[idx]*L[idx] >= rem) {
        sc = rem/L[idx] + (rem%L[idx] != 0);
      } else {
        LL z = rem-B[idx]*L[idx];
        sc = B[idx] + z/U[idx] + (z%U[idx] != 0);
      }
    }
    assert(sc <= Z);
    MN(ans, cnt*Z + sc);
  }
  cout << ans << endl;
}


Measured memory_bytes: 5104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string S;

int main() {
    cin >> S;

    string ans = "";
    for (int i = 0; i < S.length(); i++) {
        if (i % 2 == 0) {
            ans += S[i];
        }
    }
    
    cout << ans << endl;

    return 0;
}


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

int main(void){

  int N;
  cin >> N;
  vector<int> a(3*N);
  for (int i=0; i<3*N; i++) cin >> a[i];

  sort((a).rbegin(), (a).rend());
  long long sum =0;
  for (int i=0; i<N; i++){
    sum += a[ i*2 + 1 ];
  }
  
  cout << sum << "\n";
}


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

#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl

typedef long long ll;

using namespace std;

void solve() {
    int A, B;
    cin >> A >> B;
    if (A > 0 && B > 0 && A < 10 && B < 10) {
        print(A * B);
    } else {
        print(-1);
    }
}

signed main() {
    solve();
}


Measured memory_bytes: 256
import sys
import numpy as np
import numba
from numba import njit
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:, :], ), cache=True)
def main(A):
    N = A.shape[0]
    INF = 1 << 60
    dp = np.full(1 << N, -INF, np.int64)
    dp[0] = 0
    for s in range(1 << N):
        x = 0
        for j in range(N):
            for i in range(j):
                if (s & (1 << j)) and (s & (1 << i)):
                    x += A[i, j]
        t = s
        while t:
            x = max(x, dp[t] + dp[s ^ t])
            t = (t - 1) & s
        dp[s] = x
    return dp[-1]

N = int(readline())
A = np.array(read().split(), np.int64).reshape(N, N)

print(main(A))

Measured memory_bytes: 107168
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<long long> monster(n + 1), player(n);
  for(int i = 0; i < n + 1; ++i) cin >> monster[i];
  for(int i = 0; i < n; ++i) cin >> player[i];
  long long ans = 0;
  for(int i = 0; i < n; ++i){
    if(player[i] > monster[i]){
      ans += monster[i];
      player[i] -= monster[i];
      if(player[i] > monster[i + 1]){
        ans += monster[i + 1];
        monster[i + 1] = 0;
      }
      else {
        ans += player[i];
        monster[i + 1] -= player[i];
      }
    }
    else {
      ans += player[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<int>p(n);
    rep(i,n)cin>>p[i];
    int c1=0,c2=0,c3=0;
    rep(i,n){
        if(p[i]<=a)c1++;
        else if(p[i]>=b+1)c3++;
        else c2++;
    }
    cout<<min({c1,c2,c3})<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
       int a,b,c, flag=0;         
       cin>>a>>b>>c;      //input memners
       if(a==b && b!=c)
              flag=1;
        if(b==c && c!=a)
              flag=1;
         if(a==c && a!=b)
              flag=1;
         if(flag==1)
               cout<<"Yes";
         else
               cout<<"No";
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

lli n;
string x;
string y;

mat dp;

int main(){
    cin >> n;
    for(lli i = 0;i < n;i++){
        cin >> x >> y;
        dp = mat(x.size()+2,vll(y.size()+2));
        for(lli i = 0;i <= x.size();i++){
            for(lli j = 0;j <= y.size();j++){
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
                dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
                if(x[i] == y[j]) dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
            }
        }
        cout << dp[x.size()][y.size()] << endl;
    }
    return 0;
}

Measured memory_bytes: 18680
N,M  =  list(map(int, input().split()))
A =  list(map(int, input().split()))
BC = [ list(map(int, input().split())) for _ in range(M)]

A.sort()
BC.sort(key = lambda x:-x[1])

i = 0 
flag = True
for b,c in BC:
    if not flag:
        break
    for _ in range(b):
        if i >=N:
            flag = False
            break
        if A[i] < c:
            A[i] = c
            i+=1 
        else:
            flag = False
            break
print(sum(A))


Measured memory_bytes: 36164
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX / 2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int n;
	cin >> n;
	map<ll, int> mp;

	ll sum = 0;
	mp[sum]++;

	rep1(i, n) {
		int a;
		cin >> a;
		sum += a;
		mp[sum]++;
	}

	ll ans = 0;
	for (auto x : mp)ans += x.second * ((ll)x.second - 1) / 2;

	cout << ans << endl;

}

Measured memory_bytes: 12800
#include<iostream>
#include<map>
#include<string>

using namespace std;

int n, best;
char s[20];
map<string, int> msi;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", s);
    string tmp = s;
    int cur = ++msi[tmp];
    if (cur > best) {
      best = cur;
    }
  }
  for (auto i = msi.begin(); i != msi.end(); ++i) {
    if (i -> second == best) {
      cout << i -> first << endl;
    }
  }
}


Measured memory_bytes: 23808
/*
	Auther:_Destiny
	time:2020.5.3
*/
#include <bits/stdc++.h>
#define ll long long
#define N 200010
#define M 1010

using namespace std;
int n;
int f[N];
map<int, int> ss;

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++)
		f[i] = read();
	for (int i = 1; i <= n; i++) {
		int x = i + f[i];
		ss[x]++;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans += ss[i - f[i]];
	cout << ans << "\n";
}

Measured memory_bytes: 21256
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////
int main(){
   int mt[] = {0, 2, 5, 5, 4, 5, 6, 3 , 7, 6};

   int n,m;
   I2(n,m);
   pair<int,int> ar[m+2];
   for(int i =1;i<=m;i++){
       I(ar[i].x);
       ar[i].y = mt[ar[i].x];
   }
   int DP[n+2];
   SETR(DP);
   DP[0] = 0;
   sort(ar + 1, ar + m+ 1);
   int ans = 0;
   int in = 0;
   
   for(int j = 1;j<=n;j++){
       for(int i = 1;i<=m;i++){
           if(j- ar[i].y >= 0 && DP[j-ar[i].y] != -1){
               DP[j] = max(DP[j], DP[j-ar[i].y] + 1);
               ans= max(ans, DP[j]);
           }
       }
   }

   in = n;
   while(in){
       for(int j = m;j>=1;j--){
           if(in- ar[j].y >= 0 && DP[in] == DP[in - ar[j].y] + 1){
               cout<<ar[j].x;
               in -= ar[j].y;
               break;
           }
       }
   }
   cout<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] A = new int[h][w];
		int[][] B = new int[h][w];
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				B[i][j] = sc.nextInt();
			}
		}
		boolean[][][] dp = new boolean[h+1][w+1][6400];
		dp[0][1][0] = true;
		dp[1][0][0] = true;
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				for(int k = 0; k < 6400; k++) {
					if(dp[i][j+1][k] || dp[i+1][j][k]) {
						int k1 = (int)Math.abs(k + A[i][j] - B[i][j]);
						if(k1 < 6400) {
							dp[i+1][j+1][k1] = true;
						}
						int k2 = (int)Math.abs(k + B[i][j] - A[i][j]);
						if(k2 < 6400) {
							dp[i+1][j+1][k2] = true;
						}
					}
				}
			}
		}
		int min = 6400;
		for(int k = 0; k < 6400; k++) {
			if(dp[h][w][k])
				min = Integer.min(k, min);
		}
		System.out.println(min);
	}
	static class FastScanner {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public FastScanner() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException 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 nextLine() {
			try {
				return reader.readLine();
			} catch(IOException e) {
				throw new RuntimeException(e);
			}
		}
	}

}


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

using namespace std;

typedef pair<string, string> key;

int n;
string s;

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

  map<key, int> m1;
  map<key, int> m2;
  for (int subset = 0; subset <= (1 << n) - 1; subset++) {
    string s11, s12, s21, s22;
    for (int i = 0; i < n; i++) {
      if (subset & (1 << i)) {
        s11.push_back(s[i]);
        s21.push_back(s[2*n-i-1]);
      } else {
        s12.push_back(s[i]);
        s22.push_back(s[2*n-i-1]);
      }
    }
    m1[make_pair(s11, s12)]++;
    m2[make_pair(s21, s22)]++;
  }

  uint64_t count = 0;
  for (auto p : m1) {
    if (m2.find(p.first) != m2.end()) {
      count += 1LL * p.second * m2[p.first];
    }
  }
  cout << count << endl;

  return 0;
}


Measured memory_bytes: 91904
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define m 1000000007
int main() {
	ll n,ans=0,i;
	cin>>n;
	if(n==2)
    {
        cout<<"1";
        return 0;
    }
	for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ll ch=n;
            while(ch%i==0)
            ch=ch/i;
            if(ch%i==1)
                ans++;
        }
    }
    for(i=2;i*i<n-1;i++)
    {
        if((n-1)%i==0)
            ans+=2;
    }
    if(i*i==n-1)
        ans++;
    cout<<ans+2<<endl;

}


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

#define PI acos(-1)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define all(c) (c).begin(), (c).end()
#define TIMESTAMP fprintf(stderr, "Execution time: %.3lf s.\n", (double)clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair <int, int> pii;
typedef vector <vi> vvi;
typedef vector <pii> vpii;
typedef vector<string> vs;

const int INF = 100500;
const int MAXN = 1e5 + 9;

int k, s;

void input() {                  
	cin >> k >> s;
}

void solve() {
	int ans = 0;
	for(int i = 0; i <= k; i++) {
		for(int j = 0; j <= k; j++) {
			int r = s - i - j;
			if(r < 0 || r > k) continue;             
			ans++;
		}
	}
	cout << ans++ << endl;		
}

int main() {     
#ifdef LOCAL
	freopen("xxx.in", "r", stdin);
	freopen("xxx.out", "w", stdout);
#else
	//freopen("xxx.in", "r", stdin);
	//freopen("xxx.out", "w", stdout);
#endif	
	input();
	solve();
	return 0;
}


Measured memory_bytes: 256
import sys

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    # max_a = 0
    # ef_i = -1
    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        # max_a = max(max_a, a[i])
        # if a[ef_i] / b[ef_i] < a[i] / b[i]:
        #     ef_i = i

    dp = [float('inf')] * (h+1)

    for point in range(h+1):
        for i in range(n):
            if point <= a[i]:
                dp[point] = min(dp[point], b[i])
                continue

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print(dp[h])


if __name__ == '__main__':
    main()


Measured memory_bytes: 43116
N = int(input())
H = list(map(int, input().split()))

cnt = 0
tmp = 0

for i in range(N-1):

    if H[i] >= H[i+1]:
        tmp += 1
    else:
        if cnt < tmp:
            cnt = tmp
        
        tmp = 0

if cnt < tmp:
    cnt = tmp

print(cnt)


Measured memory_bytes: 14252
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while (true) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			int H = sc.nextInt();
			int K = sc.nextInt();
			if (N == 0) break;
			int[] v = new int[N];
			for (int i = 0; i < N; ++i) {
				v[i] = sc.nextInt();
			}
			int[] bar = new int[M];
			for (int i = 0; i < M; ++i) {
				int a = sc.nextInt() - 1;
				int b = sc.nextInt();
				bar[i] = (b << 10) + a;
			}
			Arrays.sort(bar);
			int[] to = new int[N];
			int[] from = new int[N];
			for (int i = 0; i < N; ++i) {
				to[i] = from[i] = i;
			}
			for (int i = M - 1; i >= 0; --i) {
				int a = bar[i] & 1023;
				swap(to, a, a + 1);
			}
			int base = 0;
			for (int i = 0; i < K; ++i) {
				base += v[to[i]];
			}
			int minDiff = 0;
			for (int i = 0; i < M; ++i) {
				int a = bar[i] & 1023;
				int fa = from[a];
				int fb = from[a + 1];
				if (fa < K && fb >= K) {
					minDiff = Math.min(minDiff, v[to[fb]] - v[to[fa]]);
				} else if (fa >= K && fb < K) {
					minDiff = Math.min(minDiff, v[to[fa]] - v[to[fb]]);
				}
				swap(from, a, a + 1);
			}
			System.out.println(base + minDiff);
		}
	}

	static void swap(int[] a, int x, int y) {
		int tmp = a[x];
		a[x] = a[y];
		a[y] = tmp;
	}

}

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

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            var inputintArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int n = inputintArray[0];
            int k = inputintArray[1];

            List<int> a = Enumerable.Range(1,n).ToList();

            for (int i = 0; i < k; i++)
            {
                var d = int.Parse(Console.ReadLine());

                inputintArray = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
                for (int j = 0; j < d; j++)
                {
                    a.Remove(inputintArray[j]);
                }
            }

            string result = a.Count.ToString();

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28664
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int h,n;
int w[1004],v[1004];
int f[10004];
int main(){
	memset(f,0x3f,sizeof(f));
	cin>>h>>n;f[0]=0;
	for(int i=1;i<=n;++i)
		cin>>w[i]>>v[i];
	for(int i=1;i<=n;++i)
		for(int j=0;j<=h;++j)
				f[min(h,j+w[i])]=min(f[min(h,j+w[i])],f[j]+v[i]);
	cout<<f[h];
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
 
#define  ll long long
#define  il inline
#define INF 0x3f3f3f3f
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define fi first
#define se second
 
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int maxm = 3e5 + 10;
const double PI = acos(-1.0);
const int inf = 1e9;



int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i < 10; i++) {
        if(n % i == 0 && n / i >= 1 && n / i <= 9){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int h,a[11][5];
main()
{
	while(cin>>h,h)
	{
		for(int i=0;i<h;i++)for(int j=0;j<5;j++)cin>>a[i][j];
		int ans=0;
		bool flag=1;
		while(flag)
		{
			flag=0;
			for(int i=0;i<h;i++)
			{
				for(int j=0;j<3;j++)
				{
					if(a[i][j]&&a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2])
					{
						ans+=a[i][j]*3;
						flag=1;
						if(j+3<5&&a[i][j]==a[i][j+3])
						{
							ans+=a[i][j],a[i][j+3]=0;
							if(j+4<5&&a[i][j]==a[i][j+4])ans+=a[i][j],a[i][j+4]=0;
						}
						a[i][j]=a[i][j+1]=a[i][j+2]=0;
					}
				}
			}
			for(int j=0;j<5;j++)
			{
				for(int i=h;i-->0;)
				{
					if(a[i][j]==0)
					{
						int k;
						for(k=i-1;k>=0&&a[k][j]==0;k--);
						if(k<0)break;
						a[i][j]=a[k][j];
						a[k][j]=0;
					}
				}
			}
		}
		cout<<ans<<endl;
	}
}



Measured memory_bytes: 3048
#include <bits//stdc++.h>
using namespace std;
#define int long long
#define rep(i,n,k) for(int i=n;i<k;i++)
#define P make_pair
#define F first
#define S second
#define M LLONG_MAX
signed main(void){
    int n,m,ans,p,q;
    ans=0;
    string s1,s2;
    vector<int> v;
    cin>>n>>m;
    int a[n];
    rep(i,0,n)
    a[i]=0;
    ans=n;
    rep(i,0,m){
        cin>>p;
        rep(j,0,p){
            cin>>q;
            a[q-1]++;
            if(a[q-1]==1)
            ans--;
        }
    }
    cout<<ans<<endl;
    
    
}


Measured memory_bytes: 3624
#include <stdio.h>

class sai{
public:
  int men[6];

  void e();
  void n();
  void s();
  void w();
  void kat();
  void kah();
};

void sai::e(){
  int t = men[0];
  men[0] = men[3];
  men[3] = men[5];
  men[5] = men[2];
  men[2] = t;
}
void sai::n(){
  int t = men[0];
  men[0] = men[1];
  men[1] = men[5];
  men[5] = men[4];
  men[4] = t;
}
void sai::s(){
  int t = men[0];
  men[0] = men[4];
  men[4] = men[5];
  men[5] = men[1];
  men[1] = t;
}
void sai::w(){
  int t = men[0];
  men[0] = men[2];
  men[2] = men[5];
  men[5] = men[3];
  men[3] = t;
}
void sai::kat(){
  int t = men[1];
  men[1] = men[2];
  men[2] = men[4];
  men[4] = men[3];
  men[3] = t;
}
void sai::kah(){
  int t = men[1];
  men[1] = men[3];
  men[3] = men[4];
  men[4] = men[2];
  men[2] = t;
}

int main(){
  sai sa, sa2;
  for(int i = 0; i < 6; i++) scanf("%d", &sa.men[i]);
  for(int i = 0; i < 6; i++) scanf("%d", &sa2.men[i]);

  for(int j = 0; j < 6; j++){
    if(sa2.men[0] == sa.men[0]){
      for(int k = 0; k < 4; k++){
        if(sa2.men[1] == sa.men[1]){
          for(int i = 2; i < 6; i++){
            if(sa.men[i] != sa2.men[i]) break;
            if(i == 5){
              printf("Yes\n");
              return 0;
            }
          }
        }
        sa.kat();
      }
    }
    if(j < 3) sa.n();
    else if(j == 3) sa.e();
    else if(j == 4){
      sa.e();
      sa.e();
    }
  }
  printf("No\n");
}



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

typedef long long ll;

typedef pair<int, pair<int, int> > p;

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

    int N, M;
    cin >> N >> M;

    vector<p> x(M);
    vector<string> ans(M);

    vector<int> count(N + 1, 1);

    for(int i = 0; i < M; i++) {
        int p, y;
        cin >> p >> y;
        x[i] = make_pair(y, make_pair(p, i));
    }

    sort(x.begin(), x.end());

    for(int i = 0; i < M; i++) {
        int p = x[i].second.first;
        int n = x[i].second.second;

        for(int j = 0; j < 6 - (log10(p) + 1); j++) {
            ans[n] += "0";
        }
        ans[n] += to_string(p);
        for(int j = 0; j < 6 - (log10(count[p]) + 1); j++) {
            ans[n] += "0";
        }
        ans[n] += to_string(count[p]);

        count[p]++;
    }

    for(int i = 0; i < M; i++) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 9728
#include "bits/stdc++.h"
#define ll long long int
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef pair<ll, ll> pairs;
typedef pair<ll, pairs> tpl;
ll dp[100001], a[100001], n, k;
ll getans(ll i)
{
	if (i >= n)
		return INT_MAX;
	if (i == n - 1)
		return 0;
	if (dp[i] != -1)
		return dp[i];
	ll ans = INT_MAX;
	for (ll j = 1; j <= k; j++)
		ans = min(ans, getans(i + j) + abs(a[i] - a[i + j]));
	return dp[i] = ans;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (ll i = 0; i < n; i++)
		cin >> a[i];
	memset(dp, -1, sizeof(dp));
	cout << getans(0);
}

Measured memory_bytes: 11348
# ABC159e

ans = 10 ** 12


def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10 ** 6)
    from copy import deepcopy
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    h, w, K = map(int, input().split())
    s = [list(map(int, list(input()))) for _ in range(h)]
    s = np.array(s).T
    s = s.tolist()
    # print(s)

    waru = set()

    def dfs(i):
        if i == h-1:
            cho = [0] * (len(waru) + 1)
            bunkatsu = [False]*(w-1)
            sl = [0]
            sl.extend(list(waru))
            sl.append(h)
            t = len(waru)
            j = 0
            while j < w:
                for k in range(1, len(sl)):
                    #print(sl[k - 1], sl[k])
                    cho[k - 1] += sum(s[j][sl[k - 1]: sl[k]])
                #print(waru, j, cho)
                for k in range(len(sl)-1):
                    if cho[k] > K:
                        if bunkatsu[j-1]:
                            return
                        cho = [0] * (len(waru) + 1)
                        bunkatsu[j-1] = True
                        t += 1
                        j -= 1
                j += 1
            #print(waru, t)
            global ans
            ans = min(ans, t)
            return
        waru.add(i+1)
        dfs(i + 1)
        waru.remove(i+1)
        dfs(i + 1)
    dfs(0)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 12596
def inpl(): return [int(i) for i in input().split()]
N = int(input())
T, A = inpl()
H = inpl()
for i in range(N):
    H[i] = (abs(T-0.006*H[i]-A),i)
H = sorted(H,key = lambda x: x[0])
print(H[0][1]+1)



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

int main()
{
    int mod = 1000000007;
    int n, m;
    cin >> n >> m;

    vector<int> oks(n + 1, true);

    for (auto i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        oks[a] = false;
    }

    vector<long long int> dp(n + 1, 0);
    dp[0] = 1;

    for (auto now = 0; now < n; now++)
    {
        for (auto next = now + 1; next <= min(n, now + 2); next++)
        {
            if (oks[next])
            {
                dp[next] += dp[now];
                dp[next] %= mod;
            }
        }
    }

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

Measured memory_bytes: 1408
# @profile
def main():
    import math

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

    # N=5
    # a = [12,15,18,36,42]

    # N = 10**5
    # a = [1]*N

    # N=11
    # a = [56,58,82,46,67,36,98,68,24,46,52]

    #a,bの最大公約数
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    # 一番近い大きい側の2の累乗の数が，segtreeの葉の数になる．
    N_ADJUST = 2**int(math.ceil(math.log(N)/math.log(2)))
    # segtreeのサイズはN_ADJUSTを葉とする木のノード数．
    ST_SIZE = N_ADJUST*2-1
    # binopに合わせて単位元として決める．maxならINT_MAX(問題文の制限)
    INT_IDENTITY = 0
    li = [INT_IDENTITY]*ST_SIZE
    # li_initは，葉の配列．
    # 節点kが [l,r) にbinopという演算で結びついている．
    def init_segtree(li, k, l, r, binop, li_init):
        if r-l==1:
            li[k] = INT_IDENTITY if l >= len(li_init) else li_init[l]
        elif r-l>1:
            k_l, k_r = k*2+1, k*2+2
            init_segtree(li, k_l, l, (l+r)//2, binop, li_init)
            init_segtree(li, k_r, (l+r)//2, r, binop, li_init)
            li[k] = binop(li[k_l],li[k_r])

    init_segtree(li,0,0,N_ADJUST,gcd,a)

    # print(li)
    # 下からupdateする．
    def update_segtree(li,k,binop):
        if k > 0:
            k_2 = (k-1)//2
            k_l = k_2*2+1
            k_r = k_l+1
            li[k_2] = binop(li[k_l],li[k_r])
            update_segtree(li,k_2,binop)

    val = []
    for i in range(N_ADJUST-1,N_ADJUST+N-1):
        tmp = li[i]
        li[i] = 0
        update_segtree(li,i,gcd)
        # print(i, li)
        val.append(li[0])
        li[i] = tmp
        update_segtree(li,i,gcd)

    print(max(val))

main()


Measured memory_bytes: 90980
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
int sleep(){
	int j=0;
	for(int i=1;i<=1000001;i++) j++;
	return j;
}
inline ll lcm(ll a,ll b) {
	return a/gcd(a,b)*b;
}
inline ll qpow(ll a,ll b) {
	ll r=1,t=a;
	while(b) {
		if(b&1)r=(r*t)%mod;
		b>>=1;
		t=(t*t)%mod;
	}
	return r;
}
inline ll inv1(ll b) {
	return qpow(b,mod-2);
}
inline ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {
		x=1;
		y=0;
		return a;
	}
	ll r=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return r;
}
inline ll read() {
	ll x=0,f=1;
	char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c); c=getchar()) x=x*10+c-'0';
	return x*f;
}
int a[100005],b[100005];
map<int,int>lisan;

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

	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);

	for(int i=1; i<=n; i++)
		lisan[b[i]]=i;

	int ans=0;
	for(int i=1; i<=n; i++) {
		int temp=abs(i-lisan[a[i]]);
		if(temp%2)
			ans++;
	}
	printf("%d\n",ans/2);
	sleep();
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int h,w,d,q;
    cin >> h >> w >> d;
    int a[h][w];
    map<int, pair<int, int>> mp;
    rep(i, h)
    {
        rep(j,w){
            cin >> a[i][j];
            a[i][j]--;
            mp[a[i][j]] = make_pair(i, j);
        }
    }
    cin >> q;
    int sum[200005] = {};
    rep(i,d){
        sum[i] = 0;
        auto start = mp[i];
        for (int j = i + d; j < h * w; j += d)
        {
            auto stop = mp[j];
            sum[j] = sum[j - d] + abs(stop.first - start.first) + abs(stop.second - start.second);
            start = stop;
        }
    }
    ll ans = 0;
    rep(i,q){
        int l,r;
        cin >> l >> r;
        l--;r--;
        cout << sum[r] - sum[l] << endl;
    }
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const int INF = 0x3f3f3f3f;
using namespace std;

int n, arr[100001];
ll dp[100002];
int main()
{
    IOS
    memset(dp, INF, sizeof dp);
    //freopen("kepler.in", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    dp[0] = 0;
    for (int i = 0; i < n-1; ++i) {
        dp[i+1] = min(dp[i+1], dp[i] + abs(arr[i+1]-arr[i]));
        if (i+2 < n) {
            dp[i+2] = min(dp[i+2], dp[i] + abs(arr[i+2]-arr[i]));
        }
    }
    cout << dp[n-1] << endl;;

    return 0;
}


Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        long N = long.Parse(Console.ReadLine());
        long[] A = new long[N];
        long[] x = new long[N];
        long s = 0;
        string[] str = Console.ReadLine().Split();
        for (var i = 0; i < N; ++i)
        {
            A[i] = long.Parse(str[i]);
            s += A[i];
        }
        x[0] = s;
        for (var i = 1; i < N; i += 2)
        {
            x[0] -= 2*A[i];
        }
        for (var i = 1; i < N; ++i)
        {
            x[i] = - x[i - 1] + 2 * A[i - 1];
        }
        Console.WriteLine(string.Join(" ", x));
    }
}

Measured memory_bytes: 32588
fun main(args: Array<String>) {
    val s = readLine()!!
    val t = readLine()!!

    val map1 = mutableMapOf<Char, Char>()
    val map2 = mutableMapOf<Char, Char>()

    var ans = true

    for (i in s.indices) {
        if (map1.containsKey(s[i])) {
            if (map1[s[i]] != t[i]) {
                ans = false
                break
            }
        } else {
            map1[s[i]] = t[i]
        }

        if (map2.containsKey(t[i])) {
            if (map2[t[i]] != s[i]) {
                ans = false
                break
            }
        } else {
            map2[t[i]] = s[i]
        }
    }

    println(if (ans) "Yes" else "No")
}


Measured memory_bytes: 37028
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;

//最大公約数
lol gcd(lol x, lol y){
  if(x < y) swap(x, y);
  lol r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}

//最小公倍数
lol lcm(lol x, lol y){
  lol a = x * y;
  return (a / gcd(x, y));
}

signed main(void){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  int a[n + 5];
  map<int, int> yakusu;
  rep(i, n){
    cin >> a[i];
    yakusu[a[i]] ++;
  }
  if(yakusu[1] == 1){
    cout << "1\n";
    return 0;
  } else if(yakusu[1] >= 2){
    cout << "0\n";
    return 0;
  }
  sort(a, a +n);
  int ans = 0;
  rep(i, n){
    bool out = false;
    for(int j = 2;j * j <= a[i];j ++){
      if(a[i] % j == 0){
	if(yakusu[j] != 0 || yakusu[a[i] / j] != 0){
	  //cout << j << '\n';
	  out = true;
	}
      }
    }
    if(!out && yakusu[a[i]] == 1){
      // cout << a[i] << " ";
      ans ++;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 33348
N=int(input())
S1=input()
S2=input()
LIST=[]
i=0
while(N>i):
    if(S1[i]==S2[i]):
        LIST.append(1)
    else:
        LIST.append(0)
        i+=1
    i+=1

s=1
t=9
for i in range(len(LIST)):
    if(t==0):
        if(LIST[i]==0):
            s*=3
        else:
            s*=1
    elif(t==1):
        if(LIST[i]==0):
            s*=2
        else:
            s*=2
    else:
        if(LIST[i]==0):
            s*=6
        else:
            s*=3
    t=LIST[i]
    s=s%1000000007
print(s)

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

int main() {
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    bool t = a > b;
    if (t) cout << a + max(a - 1, b) << endl;
    else cout << b + max(b - 1, a) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;

typedef vector<lint> vl;
typedef pair<lint,lint> pll;

#define mpr make_pair

int main()
{
    ios_base::sync_with_stdio(0);    cin.tie(NULL);    cout.tie(NULL);

    int k; cin>>k;
    string s; cin>>s;

    if (s.size()<=k){
        cout<<s;
    }else{
        cout<<s.substr(0, k)+"...";
    }

}


Measured memory_bytes: 3652
max = -20000000000
ri = 0
count = 0;
STDIN.each_line {|line|
  if count == 0
    count = 1
    next
  end
  
  now_value = line.to_i
  if ri == 0
    ri = now_value
    next
  end

  if max < (now_value - ri)
    max = now_value - ri
  end

  if ri > now_value
    ri = now_value
  end
}

print max, "\n"



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

typedef long long ll;
#define rep(i, s, n) for(int i=s;i<n;i++)
#define repeq(i,s,n) for(int i=s;i<=n;i++)
#define MOD 10e9+7

void max_self(int& a, int b) { a=a>b?a:b; }
void min_self(int& a, int b) { a=a<b?a:b; }

using namespace std;

int temp;
ll curr;
bool found;
int n, x;

int i = 0;

int main() {

    cin >> n >> x;

    for(i = 2; i < n+2; i++) {
        cin >> temp;
        curr+=temp;
        if(curr > x) {
            found = true;
            cout << i-1;
            break;
        }
    }

    if(!found)
        cout << (n+1);
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;	
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String[] c = new String[n];
		for(int i = 0;i < n;i++) {
			c[i] = sc.next();
		}
		for(int i = 0;i < m+2;i++)System.out.print("#");
		System.out.println();
		for(int i = 0;i < n;i++) {
			System.out.println("#"+c[i]+"#");
		}
		for(int i = 0;i < m+2;i++)System.out.print("#");
		System.out.println();
	}

}



Measured memory_bytes: 21844
import sys
from collections import defaultdict

n = int(input())
stones = [-1]
for line in sys.stdin:
    c = int(line)
    if stones[-1] == c:
        continue
    stones.append(c)

dp = 1
prev = defaultdict(lambda: 0)
MOD = 10 ** 9 + 7
for s in stones[1:]:
    dp = (dp + prev[s]) % MOD
    prev[s] = dp
print(dp)


Measured memory_bytes: 31336
#include <stdio.h>
void temp(int *x, int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

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

    if(a > b) temp(&a, &b);
    if(a > c) temp(&a, &c);
    if(b > c) temp(&b, &c);

    printf("%d %d %d\n",a, b, c);
    
    return 0;
}


Measured memory_bytes: 2064
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] stu = new int[n];
		int[] res = new int[n];
		for(int i = 0; i < n; i++){
			stu[i] = sc.nextInt();
		}
		for(int i = 0; i < n;i++){
			res[stu[i] - 1]= i + 1;
		}
		for(int i: res){
			System.out.print(i + " ");
		}
	}
}

Measured memory_bytes: 61156