akhauriyash/Code-Regression huggingface dataset:
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize ("-ffloat-store")

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

#ifdef ARYANC403
#include "/home/aryan/codes/PastCodes/header.h"
#else
    #define dbg(args...)
#endif

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    map<string,lli> m;
    cin>>n;
    while(n--)
    {
        cin>>s;
        m[s]++;
    }

    cin>>n;
    while(n--)
    {
        cin>>s;
        m[s]--;
    }
    cnt=0;
    for(auto s:m)
        cnt=max(cnt,s.Y);
    cout<<cnt<<endl;
}   aryanc403();
    return 0;
}


Measured memory_bytes: 3604
/**
 * Author RDP
 * 
**/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0);
typedef long long ll;
using namespace std;

void test_case()
{
    FAST_IO
    ll d, n;
    cin >> d >> n;
    int ex;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >>ex;
        d -= ex;
    }
    if(d<0)
        cout << "-1" <<endl;
    else 
        cout << d <<endl;
    return ;
}
int main()
{
    FAST_IO
    test_case();
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    int a[n][3];
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    int dp[n][3]={0};
    dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
    for(int i=1;i<n;i++){
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a[i][0];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2])+a[i][1];
        dp[i][2] = max(dp[i-1][1],dp[i-1][0])+a[i][2];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
}


Measured memory_bytes: 2560
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var n = Sarray()[0];
            var vi = Sarray();
            var dct = new long[2].Select(_ => new Dictionary<long, long>()).ToArray();
            var cnt = 0L;
            foreach(var v in vi)
            {
                var t = cnt++ % 2;
                if (!dct[t].ContainsKey(v)) dct[t][v] = 0;
                ++dct[t][v];
            }
            var lst0 = dct[0].Select(kv => (kv.Key, kv.Value)).OrderByDescending(k => k.Value).ToList();
            var lst1 = dct[1].Select(kv => (kv.Key, kv.Value)).OrderByDescending(k => k.Value).ToList();
            var sum = lst0[0].Value + lst1[0].Value;
            if (lst0[0].Key == lst1[0].Key)
            {
                lst0.Add((0, 0));
                lst1.Add((0, 0));
                sum = Max(lst0[0].Value + lst1[1].Value, lst0[1].Value + lst1[0].Value);
            }
            WriteLine(n - sum);
        }


        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

Measured memory_bytes: 46516
#  = gets.chomp.to_i
N, K, Q = gets.chomp.split.map(&:to_i)
# S = gets.chomp

## Ex.
# answer by 0
# => [K, K-1, ..., K-1]

# We want to calculate the maximum difference of (Q + A[i] - K)
# score[i] is the coreect count of each player-i.

scores = Array.new(N, K - Q)
Q.times do
  i = gets.chomp.to_i - 1
  scores[i] += 1
end

scores.each do |score|
  if score > 0
    print "Yes\n"
  else 
    print "No\n"
  end
end


Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1 << 18;
#define int long long
typedef pair<int,int> P;
int n;
P dat[2*MAX_N-1];
void init(int n_){
  n=1;
  while(n<n_) n*=2;
  for(int i=0;i<2*n-1;i++) dat[i].first=-1,dat[i].second=INT_MAX;
}
int query(int k){
  k+=n-1;
  P p=dat[k];
  //cout<<k<<"/"<<dat[k].second<<endl;
  while(k>0){
    k=(k-1)/2;
    //cout<<k<<"/"<<dat[k].second<<endl;
    p=max(p,dat[k]);
  }
  return p.second;
}

void update(int a,int b,int k,P p,int l,int r){
  if(r<=a||b<=l) return;
  if(a<=l&&r<=b) {
    //cout<<a<<":"<<b<<":"<<k<<":"<<l<<":"<<r<<endl;
     dat[k]=p;
  }else{
    update(a,b,k*2+1,p,l,(l+r)/2);
    update(a,b,k*2+2,p,(l+r)/2,r);
  }
}
signed main(){
  int _n,q;
  cin>>_n>>q;
  init(_n+1);
  for(int i=0;i<q;i++){
    int f;
    cin>>f;
    if(!f){
      int s,t,x;
      cin>>s>>t>>x;
      //cout<<i<<":"<<x<<endl;
      update(s,t+1,0,P(i,x),0,n);
    }else{
      int u;
      cin>>u;
      cout<<query(u)<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 11288
#include<bits/stdc++.h>
using namespace std;
list<int> l[1010];
int main()
{
	int n, m;
	list<int>::iterator it;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int x;
		scanf("%d",&x);
		if(x == 0)
		{
			int y, z;
			scanf("%d%d",&y,&z);
			l[y].push_back(z);
		}
		else if(x == 1)
		{
			int y;
			scanf("%d",&y);
			for(it=l[y].begin(); it!=l[y].end(); it++)
			{
				if(it != l[y].begin()) printf(" %d",*it);
				else printf("%d",*it);
			}
			printf("\n");
		
		}
		else if(x == 2)
		{
			int y, z;
			scanf("%d%d",&y,&z);
			l[z].splice(l[z].end(), l[y]);
		}
	}
	return 0;
}


Measured memory_bytes: 18824
#include<bits/stdc++.h>
using namespace std;
namespace FastIO
{
	static char c;
	static int top,buf[12],f;
	template<typename T>
	inline void read(T& x)
	{
		x=0,c=getchar(),f=1;
		while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
		while(isdigit(c))x=x*10+c-'0',c=getchar();x*=f;
	}
	template<typename T>
	inline void write(T x,int f=0)
	{
		top=0;
		if(x<0)putchar('-'),x=-x;
		do buf[top++]=x%10,x/=10;while(x);
		for(int i=top-1;~i;i--)putchar(buf[i]+48);
		if(f)putchar(f&1?' ':'\n');
	}
}
using FastIO::read;
using FastIO::write;

int H,W,h,w,a[505];

int main()
{
	read(H),read(W),read(h),read(w);
	if(H%h==0&&W%w==0)return puts("No"),0;
	puts("Yes");
	if(W%w)
	{
		for(int i=1;i<=W;i+=w)a[i]=1e9-1;
		for(int i=w;i<=W;i+=w)a[i]=-1e9;
		for(int i=1;i<=H;i++)
		{
			for(int j=1;j<=W;j++)write(a[j],1);
			putchar('\n');
		}
	}
	else
	{
		for(int i=1;i<=H;i+=h)a[i]=1e9-1;
		for(int i=h;i<=H;i+=h)a[i]=-1e9;
		for(int i=1;i<=H;i++)
		{
			for(int j=1;j<=W;j++)write(a[i],1);
			putchar('\n');
		}
	}
	return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define LLMAX (1ll << 60) - 1
#define INTMAX (1 << 30) - 1
#define MOD 1000000007 
#define NMAX 1000*100+1
#define MSET(x,y) memset(x,y,sizeof(x))
#define gcd(a,b) __gcd(a,b)
#define all(x)  x.begin(),x.end()
#define vi vector<int>
#define print(x)    for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<endl;
#define in(x,n)   for(int e=0;e<n;e++){int y;cin>>y;x.pb(y);}
ll dp[100001],h[100001];

ll func(int x){
	if(dp[x]!=-1){
		return dp[x];
	}
	
	if(x==0){
		return 0;
	}
	if(x==1){
		return abs(h[x]-h[x-1]);
	}
	return dp[x] = min(func(x-1)+abs(h[x]-h[x-1]),func(x-2)+abs(h[x]-h[x-2]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,x;
    MSET(dp,-1);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    cout<<func(n-1);

    
    

    return 0;
}




Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, X[100010], A[100010]; 
	cin >> N; 
	for(int i = 1; i <= N; i++){
		cin >> X[i]; 
		int tmp = i - 1 - (X[i] - 1) / 2; 
		A[i] = max(A[i-1], tmp); 
	}
	long long P = 1000000007; 
	long long ans = 1LL; 
	for(int i = 1; i <= N; i++){
		ans *= (long long) i - A[i-1]; 
		ans %= P; 
	}
	cout << ans << endl; 
}

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

using namespace std;

int main(){
    int k, n;
    cin >> k >> n;
    vector<int> v(n);
    for(int& i:v) cin >> i;
    sort(v.begin(), v.end());
    v.push_back(k+v[0]);
    int ans = 0;
    for(int i = 1; i < n+1; i++) ans = max(ans, v[i] - v[i-1]);
    cout << k-ans << '\n';
}

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

int main() {

  int n;
  int data[1001];
  int dp[1001][1<<3];

  cin >> n;

  for(int i=1; i<=n; i++) {
    char c;
    cin >> c;
    if( c == 'J' ) data[i] = 0;
    if( c == 'O' ) data[i] = 1;
    if( c == 'I' ) data[i] = 2;
    for(int j=1; j<(1<<3); j++) {
      dp[i][j] = 0;
    }
  }

  dp[0][1] = 1;

  for(int i=1; i<=n; i++) {
    for(int j=1; j<(1<<3); j++) {
      if( dp[i-1][j] ) {
	for(int k=1; k<(1<<3); k++) {
	  if( (k & j) && (k & (1 << data[i])) ) {
	    dp[i][k] += dp[i-1][j];
	    dp[i][k] %= 10007;
	  }
	}
      }
    }
  }

  int ans = 0;
  for(int i=1; i<(1<<3); i++) {
    ans += dp[n][i];
  }

  cout << ans % 10007 << endl;
}

Measured memory_bytes: 1192
def gen_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    return divisors


N = int(input())

divisors = gen_divisors(N)
divisors.remove(1)
ans = 0
for d in divisors:
    m = d-1
    if N//m == N%m:
        ans += m

print(ans)


Measured memory_bytes: 3276
#include<iostream>
using namespace std;
int main() {
  string a,b;
  cin >> a >> b;
  if(a[0] == b[2] && a[1] == b[1] && a[2] == b[0]) {
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> P;

#define NODE 110

int main()
{
  int N, M, L, K, A, H;

  while (1) {
    cin >> N >> M >> L >> K >> A >> H;
    if (!(N|M|L|K|A|H)) break;

    vector<int> ccity(L);
    REP(i, L) cin >> ccity[i];

    long long dist[NODE][NODE];
    REP(i, NODE) REP(j, NODE) dist[i][j] = LLINF;
    REP(i, NODE) dist[i][i] = 0;
    REP(i, K) {
      int X, Y, T;
      cin >> X >> Y >> T;
      dist[X][Y] = dist[Y][X] = T;
    }

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

    long long cdist[NODE][NODE];
    REP(i, NODE) REP(j, NODE) cdist[i][j] = LLINF;
    REP(i, NODE) cdist[i][i] = 0;
    REP(i, L) {
      int c = ccity[i];
      if (dist[A][c] <= M) cdist[A][c] = cdist[c][A] = dist[A][c];
      if (dist[c][H] <= M) cdist[c][H] = cdist[H][c] = dist[c][H];
      REP(j, ccity.size()) {
        if (dist[c][ccity[j]] <= M)
          cdist[c][ccity[j]] = cdist[ccity[j]][c] = dist[c][ccity[j]];
      }
    }
	if (dist[A][H] <= M) cdist[A][H] = cdist[H][A] = dist[A][H];


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

    if (cdist[A][H] >= LLINF) cout << "Help!" << endl;
    else if (cdist[A][H] > M) cout << (2*cdist[A][H] - M) << endl;
    else cout << cdist[A][H] << endl;
  }

	return 0;
}



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

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
   if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d))cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
      }


Measured memory_bytes: 256
import numpy as np
import math

N, H = [int(_) for _ in input().split()]
a_arr=np.zeros(N).astype(int)
b_arr=np.zeros(N).astype(int)
for i in range(N):
    a,b=[int(_) for _ in input().split()]
    a_arr[i]=a
    b_arr[i]=b
    
ma=a_arr.max()

s_arr=np.sort(b_arr)[::-1]
count=0
for i in range(N):
    if (s_arr[i]<=ma) or (H<=0):
        break
    count+=1
    H-=s_arr[i]

if H>0:
    count+=math.ceil(H/ma)
print(count)

Measured memory_bytes: 16100
from math import sqrt

n, k = map(int, input().split())
k = float(k)
ans = 0
for _ in range(n):
    x, y = map(float, input().split())
    x,y = abs(x), abs(y)
    dist = (x**2 + y**2)**(0.5)
    if dist <= k:
        ans += 1
print(ans)


Measured memory_bytes: 9328
#include <iostream>

static int MAX = 10000;

int main()
{
  int N;      //家の数
  int a[MAX]; //家の座標
  int min_a=1000;  //最小座標
  int max_a=0;  //最大座標
  int length; //最小移動距離

  std::cin >> N;
  for(int i=0;i<N;++i){
    std::cin >> a[i];
    if(a[i]<min_a) min_a = a[i];
    if(a[i]>max_a) max_a = a[i];
  }

  length = max_a - min_a;
  std::cout << length << '\n';

  return (0);
}


Measured memory_bytes: 256
using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define N_MAX (100010)

int main(){

    int n;
    int v[N_MAX];
    
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> v[i];              
    }

    map<int, int> mp1, mp2;
    for(int i = 0; i < n; i += 2) mp1[v[i]]++;
    for(int i = 1; i < n; i += 2) mp2[v[i]]++;
    
    int mp1_1st_v = 0;
    int mp1_1st_c = 0;
    int mp1_2nd_v = 0;
    int mp1_2nd_c = 0;

    for(auto it : mp1){
        if(it.second > mp1_1st_c){
            mp1_1st_v = it.first;
            mp1_1st_c = it.second;
        }
    }

    mp1.erase(mp1_1st_v);

    for(auto it : mp1){
        if(it.second > mp1_2nd_c){
            mp1_2nd_v = it.first;
            mp1_2nd_c = it.second;
        }
    }

    //cout << mp1_1st_v << " " << mp1_1st_c << endl;
    //cout << mp1_2nd_v << " " << mp1_2nd_c << endl;

    int mp2_1st_v = 0;
    int mp2_1st_c = 0;
    int mp2_2nd_v = 0;
    int mp2_2nd_c = 0;

    for(auto it : mp2){
        if(it.second > mp2_1st_c){
            mp2_1st_v = it.first;
            mp2_1st_c = it.second;
        }
    }

    mp2.erase(mp2_1st_v);

    for(auto it : mp2){
        if(it.second > mp2_2nd_c){
            mp2_2nd_v = it.first;
            mp2_2nd_c = it.second;
        }
    }

    //cout << mp2_1st_v << " " << mp2_1st_c << endl;
    //cout << mp2_2nd_v << " " << mp2_2nd_c << endl;


    int ans;

    if(mp1_1st_v == mp2_1st_v){
        ans = min(n-(mp1_1st_c+mp2_2nd_c),n-(mp1_2nd_c+mp2_1st_c));
    }else{
        ans = n-(mp1_1st_c+mp2_1st_c);
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 5376
#include <bits/stdc++.h> //library
#define rep(i, n) for(int i = 0; i < (int)(n); i++) //for-loop (from 0)
#define reps(i,n) for(int i = 1; i <= (int)(n); i++) //for-loop (from 1)
#define all(x) (x).begin(),(x).end() //start-to-end iteration, mainly in upper_bound, lower_bound
#define SZ(x) ((int)(x).size()) //unsigned to signed

using namespace std;
using ll = long long; //long long
ll M = 1000000000 + 7;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } //compare a,b and replace by greater
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } //compare a,b and replace by smaller
ll qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; } //power
ll qp(int a, ll b, ll Mod = M) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%Mod; a = 1ll * a*a%Mod; } while (b >>= 1); return ans; } //power(mod)
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } //gcd
int dx[4] = { 1,0,-1,0 }; //path
int dy[4] = { 0,1,0,-1 }; //path
ll RS(ll N, ll P, ll Mod = M) { if (P == 0)return 1; else if (P % 2 == 0) { ll sq = RS(N, P / 2, Mod); return sq*sq%Mod; } else { return N*RS(N, P - 1, Mod) % Mod; } } //power(mod)(repeat-square,fast)
ll nPr(ll n, ll r, ll Mod = M) { ll ans = 1; rep(i, r) { ans = ans * (n - i) % Mod; } return ans; } //permutation
ll nCr(ll n, ll r, ll Mod = M) { ll bunbo = 1; ll bunshi = 1; rep(i, r) { bunbo = bunbo * (i + 1) % Mod; bunshi = bunshi * (n - i) % Mod; } return bunshi * RS(bunbo, Mod - 2, Mod) % Mod; } //combination

int main(void) {
  int n; cin >> n;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  
  vector<int> dp(n);
  dp[0] = 0; dp[1] = abs(h[0]-h[1]);
  for (int i = 2; i < n; i++){
    dp[i] = min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]));
  }
  
  cout << dp[n-1] << endl;
  return 0;
}

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

int main() {
	long long int X;
	cin >> X;

	int year = 0;
	long long int money = 100;
	while (1) {
		year++;
		money += money / 100;
		if (money >= X) {
			cout << year << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    s.erase(unique(all(s)), s.end());
    put(s.size());
    


    return 0;
}

Measured memory_bytes: 3744
#![allow(unused)]

use std::{cmp, collections, fmt, io, iter, ops, str};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($fmt: expr) => { eprintln!($fmt) };
    ($fmt: expr, $($arg: tt)*) => { eprintln!($fmt, $($arg)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($fmt: expr) => {};
    ($fmt: expr, $($arg: tt)*) => {};
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if buf.len() > 0 {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn main() {
    let a_price = parse_word::<i32>();
    let b_price = parse_word::<i32>();
    let ab_price = parse_word::<i32>();

    let calc_price = |a, b, ab| a as i32 * a_price + b as i32 * b_price + ab as i32 * ab_price;

    let a_num = parse_word::<usize>();
    let b_num = parse_word::<usize>();

    let mut a_buy = a_num;
    let mut b_buy = b_num;
    let mut ab_buy = 0;
    let mut price = calc_price(a_buy, b_buy, ab_buy);

    loop {
        debug!(
            "a: {}, b: {}, ab: {}, price: {}",
            a_buy,
            b_buy,
            ab_buy,
            calc_price(a_buy, b_buy, ab_buy)
        );

        if a_buy == 0 && b_buy == 0 {
            break;
        }

        let new_a_buy = a_buy - if a_buy > 0 { 1 } else { 0 };
        let new_b_buy = b_buy - if b_buy > 0 { 1 } else { 0 };
        let new_ab_buy = ab_buy + 2;

        let new_price = calc_price(new_a_buy, new_b_buy, new_ab_buy);
        if new_price > price {
            break;
        }

        a_buy = new_a_buy;
        b_buy = new_b_buy;
        ab_buy = new_ab_buy;
        price = new_price;
    }

    println!("{}", calc_price(a_buy, b_buy, ab_buy));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}


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

int main() {
    string s;
    cin >> s;
    if (s == "SUN") cout << 7 << endl;
    else if (s == "MON") cout << 6 << endl;
    else if (s == "TUE") cout << 5 << endl;
    else if (s == "WED") cout << 4 << endl;
    else if (s == "THU") cout << 3 << endl;
    else if (s == "FRI") cout << 2 << endl;
    else cout << 1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void print(string S,int N,char m){
  if(N==0)cout<<S<<endl;
  else for(char a='a';a-m<=1;a++)print(S+a,N-1,max(a,m));
}
int main(){
  int N;cin>>N;string S="a";
  print(S,N-1,'a');
}

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

template<typename T>
vector<T> dijkstra(const vector<vector<pair<int, T>>> &g, int s, T inf, T zero
    /* vector<int> prev */) {
  using PTI = pair<T, int>;
  int n = g.size();
  vector<T> d(n, inf);
  priority_queue<PTI, vector<PTI>, greater<PTI>> Q;
  d[s] = zero; Q.push({d[s], s});
  while (!Q.empty()) {
    int p = Q.top().second; Q.pop();
    for (const auto &f : g[p]) {
      int to = f.first; T cost = f.second;
      if (d[to] > d[p] + cost) {
        d[to] = d[p] + cost;
        /* prev[to] = p; */
        Q.push({d[to], to});
      }
    }
  }
  return d;
}

using ll = int64_t;

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

int main() {
  ll n, m, s, t; cin >> n >> m >> s >> t;
  s--, t--;
  vector<vector<pair<int,ll>>> g(n), h(n);
  ll a, b, u, v;
  rep(i,m) {
    cin >> u >> v >> a >> b;
    u--, v--;
    g[u].push_back({v, a});
    g[v].push_back({u, a});
    h[u].push_back({v, b});
    h[v].push_back({u, b});
  }

  vector<ll> dg, dh;
  dg = dijkstra(g, s, (1L << 60), 0L);
  dh = dijkstra(h, t, (1L << 60), 0L);
  vector<ll> ans(n);
  ans[n-1] = dg[n-1] + dh[n-1];
  for (int i = n-1; i > 0; --i) {
    ans[i-1] = min(ans[i], dg[i-1] + dh[i-1]);
  }
  rep(i,n) {
    cout << 1000000000000000L - ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 19012
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define max(a, b)	(((a) > (b)) ? (a) : (b))		/* ２個の値の最大値 */
#define min(a, b)	(((a) < (b)) ? (a) : (b))		/* ２個の値の最小値 */
#define ENTER		printf("\n")					/* 改行プリント */
int DBG = 1;										/* デバッグプリント 提出時は0 */
/* main *************************************************************/

#define PI 3.141592653589793

int main()
{
	int		a,b,x;

	double  m,aa,bb,ans,mm;

	scanf("%d %d %d", &a, &b ,&x);
	
	m = (double)x/a;
	
	if ( (double)m <= (double)a*b/2 ) {
		aa = m/b*2;
		ans = atan( (double)b / aa)*180/PI;
		//printf("aa/b %f\n",aa/b);
	} else {
		mm = m - (double)a*b/2;
		m = (double)a*b/2 - mm;
		bb = m/a*2;
		ans = 90 - atan( (double)a / bb)*180/PI;
	}
	
	printf("%f\n",ans);

	//printf("%f %f\n",tan(45),atan(1));

	return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int n;
  int64 m;
  int v;
  int p;
  cin >> n >> m >> v >> p;
  vector<int64> xs(n);
  for (int i = 0; i < n; i++) {
    cin >> xs[i];
  }
  sort(xs.begin(), xs.end());
  reverse(xs.begin(), xs.end());

  int ans = 0;
  ans += p;

  if (v <= p) {
    for (int k = p; k < n; k++) {
      if (xs[k] + m >= xs[p - 1]) ans++;
      else break; 
    } 
  } else {
    int64 capacity = 0;
    for (int k = p; k < n; k++) {
      if (xs[k] + m < xs[p - 1]) break;
      
      if (k == p) {
        capacity = (xs[p] + m - xs[p - 1]) + m * (n - p - 1);
      } else {
        capacity -= (xs[k - 1] - xs[k]) * (k - p);
        capacity -= m;
        capacity += (xs[k] + m - xs[k - 1]);
      }

      if (DEBUG) {
        cout << "k: " << k << " capacity: " << capacity << endl;
      }

      if (capacity < m * (v - p)) break;

      ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 1152
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())

s = {"r": P, "s": R, "p": S}
res = 0
for i in range(N):
    if i >= K:
        if T[i] == T[i-K]:
            T[i] = 0
            continue
    res += s[T[i]]

print(res)

Measured memory_bytes: 4084
s=input()
exc_x=""
cnt=[]
now=0
for i in s:
    if i=="x":
        now+=1
    else:
        cnt.append(now)
        now=0
        exc_x+=i
cnt.append(now)
if exc_x!=exc_x[::-1]:
    print(-1)
    exit()
ans=0
n=len(cnt)
for i in range(n//2):
    ans+=abs(cnt[i]-cnt[n-i-1])
print(ans)

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




int K, T;
int a[100];
//-----------------------------------------------------------------
int solve() {
	int m = a[0];

	int ans = 0;

	int mm = (K + 1) / 2;
	if (m <= mm) return 0;

	return m - (K - m + 1);
}
//-----------------------------------------------------------------
int main() {
	cin >> K >> T;
	rep(i, 0, T) cin >> a[i];
	sort(a, a + T, greater<int>());

	cout << solve() << endl;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

t = max(a)
num_list = [0] * (t + 2)

for i in range(n):
    num_list[a[i]] += 1
    if a[i] == 0:
        continue
    else:
        num_list[a[i]-1] += 1
    if a[i] == t:
        continue
    else:
        num_list[a[i]+1] += 1

print(max(num_list))

Measured memory_bytes: 14008
#include <bits/stdc++.h>
using namespace std;
int main(){
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=1;k*i<=b;i++){
        if(k*i>=a&&k*i<=b){
            cout<<"OK";
            return 0;
        }
    }
    cout<<"NG";
}


Measured memory_bytes: 3636
dc = gets.split.map(&:to_i)
q = gets.to_i
q.times do
  t,f = gets.split.map(&:to_i).map{|i| dc.index(i)+1}
  case t
  when 1,6
    s = [2,3,5,4]
    while (s[0] != f) do
      s.unshift(s.pop)
    end
    puts (t == 1) ? dc[s[1]-1] : dc[s[-1]-1]
  when 2,5
    s = [1,4,6,3]
    while (s[0] != f) do
      s.unshift(s.pop)
    end
    puts (t == 2) ? dc[s[1]-1] : dc[s[-1]-1]
  when 3,4
    s = [1,2,6,5]
    while (s[0] != f) do
      s.unshift(s.pop)
    end
    puts (t == 3) ? dc[s[1]-1] : dc[s[-1]-1]
  end
end

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

int main()
{
	int x;
	int y;
	char a,b;
	cin >> a;
	cin >> b;
	
	if(a=='A')
	{
		x=10;
	}else if (a=='B')
	{
		x=11;
	}else if (a=='C')
	{
		x=12;
	}else if (a=='D')
	{
		x=13;
	}else if (a=='E')
	{
		x=14;
	}else if (a=='F')
	{
		x=15;
	}
	
	if(b=='A')
	{
		y=10;
	}else if (b=='B')
	{
		y=11;
	}else if (b=='C')
	{
		y=12;
	}else if (b=='D')
	{
		y=13;
	}else if (b=='E')
	{
		y=14;
	}else if (b=='F')
	{
		y=15;
	}
	
	if (x>y)
	{
		cout << '>'<< endl;
	}
	else if(x<y)
	{
		cout << '<'<< endl;
	}else
	{
		cout << "="<< endl;
	}
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	long mod = 1000000007;

	private long fact(long x) {
		long ans = 1;
		for (long i = 1; i <= x; i++) {
			ans *= i;
			ans %= mod;
		}
		return ans;
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		sc.close();

		if (N < M) {
			int tmp = N;
			N = M;
			M = tmp;
		}
		if (N - M > 1) {
			out.println(0);
			return;
		}

		//Nの並べ方*Mの並べ方
		long ans = fact(N) * fact(M);
		ans %= mod;

		if (N == M) { //同数なら猿犬猿犬と犬猿犬猿が可能なので2倍。
			ans *= 2;
			ans %= mod;
		}
		out.println(ans);

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
   int n,a,b,c,l[20],ans=1e9+7,N,m;
   cin>>n>>a>>b>>c;
   for(int i=1;i<=n;i++) cin>>l[i],
   N=pow(4,n);
   for(int i=0;i<N;i++)
   {
   	  int A=0,B=0,C=0;m=0;
   	  int x=i;
   	  for(int j=1;j<=n;j++){
   	  	if(x%4==1) {if(A>0) m+=10;A+=l[j]; }	
   	  	if(x%4==2) {if(B>0) m+=10;B+=l[j]; }	 
   	  	if(x%4==3) {if(C>0) m+=10;C+=l[j];  }
   	  	x=x/4;
		 }
		 if(A==0||B==0||C==0) continue;
		 m+=abs(A-a)+abs(B-b)+abs(C-c); //cout<<m<<" ";
		 ans=min(ans,m);
   }
  
  cout<<ans;

return 0;
}


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

class Solve {
private:
	struct Segment {
		int64_t num{}, length{};
		std::vector<bool> left, right;
	};

	std::string S, Q;
	int Slength, Qlength;
	std::vector<Segment> charSegment;
	Segment zeroSegment;
	
	Segment calcGenomes(int& s_i)
	{
		Segment ret{zeroSegment};
		while (s_i != Slength && S[s_i] != ')')
			ret = segmentMultiple(ret, calcOneGenome(s_i));
		return ret;
	}

	Segment calcOneGenome(int& s_i)
	{
		Segment ret;
		if (isupper(S[s_i]))
		{
			ret = charSegment[S[s_i] - 'A'];
			s_i++;
		}
		else
		{
			int64_t exponential{calcNumber(s_i)};
			if (S[s_i] == '(')
			{
				s_i++;
				Segment base{calcGenomes(s_i)};
				s_i++;
				ret = binExponent(base, exponential);
			}
			else
			{
				Segment base{charSegment[S[s_i] - 'A']};
				s_i++;
				ret = binExponent(base, exponential);
			}
		}
		return ret;
	}

	int64_t calcNumber(int& s_i)
	{
		int64_t ret{};
		while (isdigit(S[s_i]))
		{
			ret = 10 * ret + S[s_i] - '0';
			s_i++;
		}
		return ret;
	}

	Segment binExponent(const Segment& base, const int64_t exponential)
	{
		Segment ret{zeroSegment}, power{base};
		for (int64_t i{exponential}; i > 0; i >>= 1, power = segmentMultiple(power, power))
			if (i & 1)
				ret = segmentMultiple(ret, power);
		return ret;
	}

	Segment segmentMultiple(const Segment& a, const Segment& b)
	{
		Segment ret;
		ret.left = a.left;
		ret.right = b.right;
		ret.num = a.num + b.num;
		ret.length = a.length + b.length;

		for (int i{1}; i < Qlength; i++)
		{
			if (a.right[i] && b.left[i])
			{
				if (i - a.length <= 0 && Qlength <= i + b.length)
					ret.num++;
			}
			else if (a.right[i])
			{
				if (i - a.length >= 0)
					ret.left[i - a.length] = false;
			}
			else if (b.left[i])
			{
				if (i + b.length <= Qlength)
					ret.right[i + b.length] = false;
			}
		}
		return ret;
	}

public:
	bool is_last_query{};
	Solve()
	{
		std::cin >> S;
		if (S == "#")
		{
			is_last_query = true;
			return;
		}
		std::cin >> Q;
		Slength = (int)S.size();
		Qlength = (int)Q.size();
		
		charSegment.resize(26);
		for (int c_i{}; c_i < 26; c_i++)
		{
			charSegment[c_i].left.resize(Qlength + 1);
			charSegment[c_i].right.resize(Qlength + 1);
			charSegment[c_i].length = 1;
			if (Q.size() == 1 && Q.front() == 'A' + c_i)
				charSegment[c_i].num = 1;
			for (int q_i{}; q_i < Qlength; q_i++)
				if (Q[q_i] == 'A' + c_i)
					charSegment[c_i].left[q_i] = charSegment[c_i].right[q_i + 1] = true;
		}
		zeroSegment.left.resize(Qlength + 1, true);
		zeroSegment.right.resize(Qlength + 1, true);

		int s_i{};
		std::cout << calcGenomes(s_i).num << std::endl;
	}
};

int main()
{
	while (!Solve().is_last_query);

	return 0;
}


Measured memory_bytes: 3176
n = int(input())

dp = [-1] * (n+1)

# def fibonacci(n):
#     if n==0 or n==1:
#         dp[n] = 1
#         return dp[n]
#     else:
#         if dp[n]!=-1:
#             return dp[n]
#         else:
#             dp[n] = fibonacci(n-1) + fibonacci(n-2)
#             return dp[n]

# ans = fibonacci(n)
# print(ans)

dp[0] = 1
dp[1] = 1

for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
typedef long long ll;
#define vint vector<int>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 100000000

ll gcm(ll a,ll b);

int main(){
  int n;
  cin >> n;
  vll A(n);
  rep(i,n) cin>> A[i];
  int count = 0;
  rep(i,n){
    while(A[i] % 2 == 0){
      A[i] /= 2;
      count++;
    }
  }
  cout << count << endl;
}






Measured memory_bytes: 384
N=int(input())

dp=[0]*(N+1)
for i in range(1,N+1):
  ans=dp[i-1]+1
  j=1
  while i>=6**j:
    ans=min(ans,dp[i-6**j]+1)
    j+=1
  j=1
  while i>=9**j:
    ans=min(ans,dp[i-9**j]+1)
    j+=1
  dp[i]=ans
  
print(ans)


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int a,b,c;
  string s;
 cin >> a >> b >> c;
  if(a < b){
    if(a < c && c < b){
      cout << "Yes";
    }else{
      cout << "No";
    }
  }else{
    if(a > c && c > b){
      cout << "Yes";
    }else{
      cout << "No";
    }
  }
}

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

vector <int> a;
void dfs(int n,int sum){
  if(sum==0){
    for(int i=0;i<a.size()-1;i++)cout <<a[i]<<" ";
    cout<<a.back()<<endl;
  }

  for(int i=min(sum,n);i>0;i--){
    a.push_back(i);
    dfs(i,sum-i);
    a.erase(--a.end());
  }
}

int main(){
  int n;
  while(cin>>n,n) dfs(n,n);
  return n;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
# define pb push_back
# define FOR(i,a,n) for(int i=a;i<n;i++)
# define mp make_pair
# define RFOR(i,a,n) for(int i=n;i>a;i--)
# define pii pair<long long int,long long int>
#define ub upper_bound
#define lb lower_bound
#define MOD 1000000007
typedef long long int ll;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
        cout.tie(0);
        ll x,y;
	cin>>x>>y;
	ll cnt=0;
	if(y>4*x)
	cnt++;
	if(2*x>y)
	cnt++;
	if(y%2==1)
	cnt++;
	if(cnt>0)
	cout<<"No"<<endl;
	else
	cout<<"Yes"<<endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <cstring>

// ---------- PBDS -----------------

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
// slow but fast ORZ :)
// ----------------------------------

using namespace std;
using namespace __gnu_pbds; 

#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(a) a.begin(), a.end()
#define MP(a, b) make_pair(a, b)
#define PB(a) push_back(a)
#define EB(a) emplace_back(a) // care when use
#define boost ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0),cout << fixed << setprecision(10);
// #define ll long long int
#define int long long int

#define DEBUG

#ifdef DEBUG

    #define debug(args...)(Debugger()) , args

    class Debugger{
        public:
        Debugger(const std::string& _separator = " | ") :
        first(true), separator(_separator){}

        template<typename ObjectType> Debugger& operator , (const ObjectType& v)
        {
            if(!first)
                std::cerr << separator;
            std::cerr << v;
            first = false;
            return *this;
        }
        ~Debugger() {  std::cerr << std::endl;}

        private:
        
        bool first;
        std::string separator;
    };

#else
    #define debug(args...)
#endif

const int N = 3003;

int dp[N][N][4];
int a[N][N];
int r, c, k;

int valid(int x, int y){
	if(x >= r or y >= c or x < 0 or y < 0){
		return 0;
	}
	return 1;
}

int fun(int row, int col, int pick){

	if(row == r-1 and col == c-1){
		if(pick != 3){
			return a[row][col];
		}else{
			return 0;
		}
	}

	if(dp[row][col][pick] != -1)
		return dp[row][col][pick];

	if(pick == 3){	
		if(valid(row, col+1))
			dp[row][col][pick] = fun(row, col+1, pick);
		if(valid(row+1, col))
			dp[row][col][pick] = max(dp[row][col][pick], fun(row + 1, col, 0));
	}else{
		if(valid(row, col+1))
			dp[row][col][pick] = max(fun(row, col+1, pick+1) + a[row][col], fun(row, col+1, pick));
		if(valid(row+1, col))
			dp[row][col][pick] = max(dp[row][col][pick], fun(row + 1, col, 0) + a[row][col]);
	}

	return dp[row][col][pick];
}

void solve(){

	cin >> r >> c >> k;

	MEM(a, 0);
	MEM(dp, -1);

	for(int i = 0; i < k; ++i){
		int rr, cc, vv;
		cin >> rr >> cc >> vv;
		rr--;
		cc--;

		a[rr][cc] = vv;
	}

	cout << fun(0, 0, 0) << "\n";

}


int32_t main(){

	boost;
	
	int T;
	
	// cin >> T;
	T = 1;
	
	while(T--){
		solve();
	}
}



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

const int N = 100010;
const ll MOD = ll(1e9 + 7);
const ll INF = 1e18;

struct Node {
	Node* l = nullptr;
	Node* r = nullptr;
	int sz;
	bool zero = false;
	int ad = 0;
	ll sum = 0;

	Node(int _sz) : sz(_sz) {
		if (sz > 1) {
			l = new Node(sz / 2);
			r = new Node(sz - sz / 2);
		}
	}

	void clear() {
		ad = 0;
		sum = 0;
		zero = true;
	}

	void apply(ll d) {
		ad = (ad + d) % MOD;
		sum = (sum + d * sz) % MOD;
	}

	void push() {
		if (zero) {
			l->clear();
			r->clear();
			zero = false;
		}
		l->apply(ad);
		r->apply(ad);
		ad = 0;
	}

	void add(int k, ll d) {
		if (sz == 1) {
			apply(d);
		} else {
			push();
			if (k < sz / 2)
				l->add(k, d);
			else
				r->add(k - sz / 2, d);
			sum = (l->sum + r->sum) % MOD;
		}
	}

	ll get(int a, int b) {
		if (b <= 0 || sz <= a)
			return 0;
		if (a <= 0 && sz <= b)
			return sum;
		push();
		return (l->get(a, b) + r->get(a - sz / 2, b - sz / 2)) % MOD;
	}
};

int n;
ll A, B;
ll a[N];

int main() {
	scanf("%d %lld %lld", &n, &A, &B);
	a[0] = -INF;
	for (int i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);

	Node* tx = new Node(n + 1);
	Node* ty = new Node(n + 1);
	tx->add(0, 1);
	ty->add(0, 1);

	int pa = 0, pb = 0;
	for (int i = 2; i <= n; ++i) {
		for (; a[i] - a[pa] >= A; ++pa);
		for (; a[i] - a[pb] >= B; ++pb);
		ll sa = tx->get(0, pb);
		ll sb = ty->get(0, pa);
		if (a[i] - a[i - 1] < A)
			tx->clear();
		if (a[i] - a[i - 1] < B) 
			ty->clear();
		ty->add(i - 1, sa);
		tx->add(i - 1, sb);
	}

	ll ans = (tx->sum + ty->sum) % MOD;
	printf("%lld\n", ans);
}


Measured memory_bytes: 21760
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

//C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others
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;
}
const int dx[8] = { -1,0,1,-1,1,-1,0,1 };
const int dy[8] = { 1,1,1,0,0,-1,-1,-1 };


//LOVE NyantakoGG	https://www.youtube.com/channel/UC6XdFs8T6Ei54O0FYl3PVVA


using namespace std;



int main() {
	int N;
	cin >> N;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		int n = 0;
		if (i % 2 == 1) {
			for (int j = 1; j <= sqrt(i); j++) {
				if (i % j == 0) {
					n++;
				}
			}
			if (2 * n == 8) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}


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

using namespace std;

int main()
{
    std::string s;
    int q;
    cin >> s;
    cin >> q;
    int t[q],f[q];
    char c[q];
    
    bool normal = true;
    std::string before = "";
    std::string after = "";
    for(int i=0; i<q; i++){
        int tmp;
        cin >> tmp;
        if(tmp == 2){
            cin >> f[i] >> c[i];
        }
        t[i] = tmp;
        //cout << "---" << endl;
        if(t[i] == 1){
            if(normal == true) normal = false;
            else normal = true;
            //cout << "Reverse!!" << endl;
            continue;
        }
        if(normal == true){
            if(f[i] == 1){
                before += c[i];
            }else{
                after += c[i];
            }
        }else{
            if(f[i] != 1){
                before += c[i];
            }else{
                after += c[i];
            }
        }
        
        //cout << before << ":" << after << "(" << normal << endl;
    }
    
    //cout << before << ":" << after << "(" << normal << endl;
    std::string ans;
    if(normal == true){
        std::reverse(before.begin(), before.end());
        ans = before + s + after;
    }else{
        std::reverse(after.begin(), after.end());
        std::reverse(s.begin(), s.end());
        ans = after + s + before;
    }

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

Measured memory_bytes: 3140
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		sc.close();
		
		int sq = (A*B)-A-B+1;
		System.out.println(sq);
	}
}


Measured memory_bytes: 23252
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && a == c && a % 2 == 0) {
        cout << -1;
        return 0;
    }
    int cnt = 0;
    while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
        cnt++;
        int na = (a + b) / 2;
        int nb = (a + c) / 2;
        int nc = (b + c) / 2;
        a = na;
        b = nb;
        c = nc;
    }
    cout << cnt;
    return 0;
}

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

int op(int a, int b) { return max(a, b); }

int e() { return 0; }

int main() {
	int N, K;
	cin >> N >> K;
	int a=0, b=0, c=0, x, y, z;
	segtree<int, op, e> seg(300000+2);
	rep(i, N) {
		cin >> x;
		y = max(x - K, 0);
		z = min(x + K, 300000);
		a = seg.prod(y, z+1) + 1;
		c = max(c, a);
		seg.set(x, a);
		// rep(i, N) std::cout << seg.get(i) << ' ';
		// std::cout << '\n';
	}
	cout << c << '\n';
}


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

using namespace std;
long long a,b;
int main()
{
	
	scanf("%lld%lld",&a,&b);
	if(a>b) swap(a,b);
	if(a*b<=0) printf("Zero\n");
	else
	{
		if(a>0) printf("Positive\n");
		else  printf(((a-b+1)%2==0)? "Positive\n":"Negative\n");
	}
}

Measured memory_bytes: 256
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def prime_fact(N):
    n = 2
    prime = []
    while n * n <= N:
        i = 0
        while N % n == 0:
            N //= n
            i += 1
        if i > 0:
            prime.append((n, i))
        n += 1
    if N != 1:
        prime.append((N, 1))
    return prime


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    cnt = [0] * (N+1)
    for n in range(1, N+1):
        prime = prime_fact(n)
        for q, e in prime:
            cnt[q-1] += e

    ret = 1
    for c in cnt:
        ret *= (c+1)
        ret %= MOD
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10076