akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

vector<string> jtob(string s) {
    vector<string> res;
    string cur = "";
    s += '/';
    for(auto c : s) {
        if(c == 'b') cur += 'b';
        else if('1' <= c and c <= '9') cur += string(c - '0', '.');
        else {
            // cerr << "# " << cur << endl;
            res.emplace_back(cur);
            cur = "";
        }
    }
    return res;
}

string btoj(vector<string> board) {
    string res = "";

    int N = board.size();
    for(size_t i=0; i<N; i++) {
        int cons = 0; board[i] += '#';
        for(auto c : board[i]) {
            if(c == '.') cons++;
            else {
                if(cons > 0) res += to_string(cons);
                cons = 0;
            }

            if(c == 'b') res += 'b';
        }
        if(i + 1 < N) res += '/';
    }
    return res;
}

int solve_testcase() {
    string s; cin >> s;
    if(s == "#") return 1;
    vector<string> board = jtob(s);

    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    x1--; y1--; x2--; y2--;
    swap(board[x1][y1], board[x2][y2]);

    string ans = btoj(board);
    cout << ans << endl;
    return 0;
}

int main() {
    while(!solve_testcase());
    return 0;
}



Measured memory_bytes: 3256
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n=parseInt(readline())
    ans=1
    mod=10^9+7
    for i in 1:n
        ans=ans*i%mod
    end
    println(ans)
end
main()

Measured memory_bytes: 111376
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
  vector<int> a;
  int tmp;
  for(int i = 0; i < 3; i++){
    cin >> tmp;
    a.push_back(tmp);
  }
  int ret = 0;
  sort(a.begin(), a.end());
  ret = (a[1] - a[0]) +(a[2] - a[1]);
  tmp = (a[2] - a[1]) +(a[1] - a[0]);
  if(tmp < ret) ret = tmp;

  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	static Scanner s=new Scanner(System.in);
	static int gInt(){
		return Integer.parseInt(s.next());
	}

	public static void main(String[] $){
		int n=gInt();
		int[]a=new int[n];
		Arrays.setAll(a,i->gInt());
		
		int sum=Arrays.stream(a).sum();
		int v=0;
		for(int i=1;i<n;++i) {
			if(Math.abs(a[i]*n-sum)<Math.abs(a[v]*n-sum)) {
				v=i;
			}
		}
		System.out.println(v);
	}
}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> d(N);
	for (int i = 0;i < N;i++) {
		cin >> d.at(i);
	}
	sort(d.begin(), d.end());
	cout << d.at(N / 2) - d.at(N / 2 - 1) << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define all(a) begin(a),end(a)
#define sz(a) (int)(a.size())
#define deb(a) cout << #a << ": " << a << ENDL;
#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;

lli to2(lli u) {
    return u * u;
}

lli dist(ii u, ii v) {
    return to2(u.f - v.f) + to2(u.s - v.s);
}

lli d;

bool z(ii u) {
    return dist(u, {0,0}) <= d * d;
}


int main()
{   _
    lli n, u, v; cin >> n >> d;
    lli cnt = 0;
    fore(i, 0, n) {
        cin >> u >> v;
        cnt += z({u, v});
    }
    cout << cnt << ENDL;
    return 0;
}


Measured memory_bytes: 3648
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}
bool solve(int n, vector<int> a) {
	int parity = 0, odds = 0, minelem = a[0];
	for (int i = 0; i < n; ++i) {
		parity = (parity + a[i] - 1) % 2;
		if (a[i] & 1) ++odds;
		minelem = min(minelem, a[i]);
	}
	if (parity == 1) return true;
	if (minelem == 1 || odds >= 2) return false;
	int g = -1;
	for (int i = 0; i < n; ++i) {
		if (a[i] & 1) --a[i];
		if (i == 0) g = a[i];
		else g = gcd(g, a[i]);
	}
	for (int i = 0; i < n; ++i) {
		a[i] /= g;
	}
	bool res = solve(n, a);
	return !res;
}
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	bool res = solve(n, a);
	cout << (res ? "First" : "Second") << endl;
	return 0;
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,ans=0,a;cin>>N;
  if(N==1)ans=1;
  else{
    for(int i=2;i<sqrt(N)+1;i++){
      for(int j=2;;j++){
        if(pow(i,j)>N)break;
        a=pow(i,j);
        ans=max(ans,a);
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 512
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    K = int(input())
    seen = [0] * K
    d = 0
    for i in range(1, 10**6+1):
        d = (d * 10 + 7) % K
        if d == 0:
            print(i)
            exit()
        if seen[d]:
            break
        seen[d] = 1
    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 71336
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define rep1(i,n)for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=(int)(n)-1;0<=i;i--)
#define rrep1(i,n) for(int i=(int)(n);1<=i;i--)

#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 

#define pcount __builtin_popcount
#define SZ(x) ((int)(x).size())
#define LEN(x) ((int)(x).length())

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define endl "\n"

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

typedef long long lint;

using namespace std;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<lint>h(n);
	rep(i,n)cin>>h[i];
	multimap<int,int>c;
	rep(i,n)c.emplace(i,i);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		a--;b--;
		c.emplace(a,b);
		c.emplace(b,a);
	}
	int ans=0;
	rep(i,n){
		bool flag=true;
		auto p = c.equal_range(i);
		for (auto it = p.first; it != p.second; ++it) {
			if((i!=(it->second))&&h[i]<=h[it->second])flag=false;
		}
		if(flag)ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 17984
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>

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

using namespace std;

int main() {
    int n,a,b;
    cin >> n>> a >>b;
    cout <<min(a*n, b)<<endl;
}

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

int main()
{
    int n;
    cin>>n;
    int a,b;
    int c=0,r=0;
    for (int i=0;i<n;i++){
        cin>>a>>b;
        if(a!=b){
          c=0;  
        }else{
            c++;
        }
        if(c>=3){
            r=1;
        }
    }
    if(r==1){
        cout<<"Yes";
    }else{
        cout<<"No";
    }

    return 0;
}

Measured memory_bytes: 3632
function main()
  myparse(x)=parse(Int,x)
  n,m=myparse.(split(readline()))
  s=[myparse.(split(readline()))[2:end] for i=1:m]
  p=myparse.(split(readline()))
  ans=0
  for i=[[i+1 for i=0:n if b&(1<<i)!=0] for b=0:(1<<n)-1]
    #すべてのsiにつながっているスイッチのオンオフのisoddがｐiと等しい
    ans += all([isodd(count(x->x∈i,s[j]))==p[j] for j=1:m])
  end
  print(ans)
end
main()

Measured memory_bytes: 132464
#include<bits/stdc++.h>
using namespace std;
long long dp[100][100001];
int n;
long long funs(int w[],int v[],int s,int wt){
   if(s==-1 || wt==0) return 0; 
   if(dp[s][wt]!=-1) return dp[s][wt];
   if(w[s]<=wt){
         return dp[s][wt]=max(funs(w,v,s-1,wt-w[s])+v[s],funs(w,v,s-1,wt));
   }
   return dp[s][wt]=funs(w,v,s-1,wt);
      
}
int main(){
  int i,j,wt;
  memset(dp,-1,sizeof(dp));
  cin>>n>>wt;
  int w[n],v[n];
  for(i=0;i<n;i++){
    cin>>w[i]>>v[i];
  }
  long long ans=funs(w,v,n-1,wt);
  cout<<ans;
  
 
}
  
  


Measured memory_bytes: 81728
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define N 1005
#define MOD 1000000007


char a[N][N];
int pos[N][N];
int dp[N][N];
		
int main(){
	int i,j,h,w;
	scanf("%d%d",&h,&w);
	for(i=0;i<h;i++){
		scanf("%s",a[i]);
	}

	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(a[i][j]=='#')
				pos[i+1][j+1] = 0;
			else
				pos[i+1][j+1] = 1; 
		}
	}

	//initialization
	for(i=1;i<=w;i++){
		if(pos[1][i]==1){
			dp[1][i]=1;
		}
		else
			break;
	}


	for(i=2;i<=h;i++){
		for(j=1;j<=w;j++){
			if(pos[i][j]==0){
				dp[i][j]=0;
			}
			else{
				dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
			}
		}
	}

	// for(i=1;i<=h;i++){
	// 	for(j=1;j<=w;j++){
	// 		printf("%d ",dp[i][j] );
	// 	}
	// 	printf("\n");
	// }

	printf("%d\n",dp[h][w] );


    return 0;
}

Measured memory_bytes: 9088
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder.XXX.B
{ 
    public class Program
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(r());
            var datas = cr();
            var cnt = 0;
            for(var i = 0; i < n;i+=2)
			{
                if(datas[i] % 2 != 0)
				{
                    cnt++;
				}

			}
            P(cnt);
        }

        private static StreamReader sr;
        public static int[] Ecr()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static string Er()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine();
        }
        public static string r()
        {
            return Console.ReadLine();
        }
        public static  int[] cr()
        {
            return Console.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static int cri()
        {
            return int.Parse(Console.ReadLine());
        }
        public static void P(string str)
        {
            Console.WriteLine(str);
        }
        public static void P(int num)
        {
            P(num.ToString());
        }
    }
}


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

def main():
    N, A, B = map(int, input().split())
    x = list(map(int, input().split()))

    ans = 0
    for i in range(N-1):
        tmp_a = (x[i+1] - x[i]) * A
        if tmp_a <= B:
            ans += tmp_a
        else:
            ans += B
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14252
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

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

struct Lonoid {
  int64_t x;
  Lonoid() {}
  Lonoid(int64_t x) : x(x) {}
  static Lonoid ident() { return Lonoid(-1); }
  static Lonoid multiply(Lonoid f, Lonoid g) {
    if (f == Lonoid::ident()) return g;
    return f;
  }
  bool operator==(const Lonoid &rhs) const { return x == rhs.x; }
};

template <typename L>
struct SegmentTree {
  int n;
  L e;
  vector<L> laz;
  SegmentTree(int n0) {
    n = 1;
    e = L::ident();
    while (n < n0) {
      n *= 2;
    }
    laz.resize(n * 2 - 1, e);
  }
  void _update(int i, L f) { laz[i] = L::multiply(f, laz[i]); }
  void update(int ql, int qr, L f) { update(ql, qr, f, 0, 0, n); }
  void update(int ql, int qr, L f, int i, int il, int ir) {
    if (qr <= il or ir <= ql) return;
    if (ql <= il and ir <= qr) {
      _update(i, f);
    } else {
      auto m = (il + ir) / 2, lch = i * 2 + 1, rch = i * 2 + 2;
      _update(lch, laz[i]);
      _update(rch, laz[i]);
      laz[i] = e;
      update(ql, qr, f, lch, il, m);
      update(ql, qr, f, rch, m, ir);
    }
  }
  L composite(int i) {
    auto f = L::ident();
    for (int k = i + n - 1; k > 0; k = (k - 1) / 2) {
      f = L::multiply(laz[k], f);
    }
    return L::multiply(laz[0], f);
  }
};

int main() {

  int n, q;
  cin >> n >> q;
  SegmentTree<Lonoid> seg(n);
  while (q--) {
    int o;
    cin >> o;
    if (o == 0) {
      int s, t;
      int64_t x;
      cin >> s >> t >> x;
      seg.update(s, t + 1, Lonoid(x));
    } else {
      int i;
      cin >> i;
      auto ans = seg.composite(i).x;
      if (ans < 0) ans = (1LL << 31) - 1;
      cout << ans << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 4944
#include <stdio.h>

#define NMAX 10000
#define NMAX1 (NMAX+1)
int n;
int group[NMAX1];

void init_group(void);
int unite(int x, int y);
int same(int x, int y);

int main(){
   int nq, iq, cmd, x, y;
   scanf("%d %d",&n,&nq);
   init_group();
   for(iq=0;iq<nq;iq++){
      scanf("%d %d %d",&cmd,&x,&y);
      switch(cmd){
      case 0 :
         unite(x,y);
         break;
      case 1 :
         same(x,y);
         break;
      }
   }
   return 0;
}

void init_group(void){
   int i;
   for(i=0;i<n;i++) group[i]=i;
}

int unite(int x, int y){
   int i, tmp, old_group, new_group;
   if( x > y ){ tmp=x; x=y; y=tmp; }
   new_group=group[x];
   old_group=group[y];
   for(i=0;i<n;i++){
      if(group[i]==old_group) group[i]=new_group;
   }
   return new_group;
}

int same(int x, int y){
   int flag;
   if(group[x]==group[y]) flag=1;
   else flag=0;
   printf("%d\n",flag);
   return flag;
}

Measured memory_bytes: 636
#include<stdio.h>

int main() {
	int n;
	int i;
	int temp;
	int a[1000] = {0};

	scanf("%d\n", &n);

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

	for (i = 0; i < n / 2 ; i++) {
		temp = a[i];
		a[i] = a[n - i - 1];
		a[n - i - 1] = temp;
	}
	
	i = 0;
	while (1) {
		printf("%d", a[i]);
		i++;

		if (i < n) {
			printf(" ");
		} else {
			printf("\n");
			break;
		}

	}

	return 0;
}


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

int main(){
  int N,M; cin >> N >> M;
  vector<int> v(N,0);
  for(int i=0; i<2*M; i++){
    int a;
    cin >> a;
    v[a-1]++;
  }
  bool f=true;
  for(int i=0; i<N; i++){
    if(v[i]%2==1) f=false;
  }
  cout << (f?"YES":"NO") << endl;
}

Measured memory_bytes: 640
N = int(input())
cnt = 0
i = 10
dp = [0,1,2,3,4,5,1,2,3,1]
while i<=N:
    idx_n,idx_s = 0,0
    while i-(9**idx_n)>=0:
        idx_n += 1
    idx_n -= 1
    while i-(6**idx_s)>=0:
        idx_s += 1
    idx_s -= 1
    dp.append(min(1+dp[i-(9**idx_n)],1+dp[i-(6**idx_s)]))
    i += 1
print(dp[N])

Measured memory_bytes: 45020
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))

def solve(k):
    cnt_d = 0
    cnt_m = 0
    ptn_dm = 0
    ans = 0
    for i in range(n):
        if s[i] == "D":
            cnt_d += 1
        if s[i] == "M":
            cnt_m += 1
            ptn_dm += cnt_d
        if s[i] == "C":
            ans += ptn_dm
        
        if i-k+1 >= 0:
            if s[i-k+1] == "D":
                cnt_d -= 1
                ptn_dm -= cnt_m
            if s[i-k+1] == "M":
                cnt_m -= 1
    return ans

for i in k:
    print(solve(i))

Measured memory_bytes: 75740
#include <iostream>

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

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(ll A, ll B) {
  cout << (B%A ? B-A:A+B) << endl;
}

int main() {
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  solve(A, B);
  return 0;
}


Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List

main = do
    n <- getSplittedLine
    let r = n !! 0
        c = n !! 1
    matrix <- forM [1..r] $ \_ -> do
        getSplittedLine
    let rMatrix = rowCalc matrix
        cMatrix = colCalc c rMatrix
        results = rMatrix ++ [cMatrix]
    mapM_ (\x -> putStrLn x) $ rowShow results


getSplittedLine :: IO [Int]
getSplittedLine = fmap (read :: String -> Int) . words <$> getLine

rowCalc :: [[Int]] -> [[Int]]
rowCalc matrix = foldr (\x acc -> (x ++ [sum x]) : acc) [] matrix

colCalc :: Int -> [[Int]] -> [Int]
colCalc n matrix = foldr (\x acc -> zipWith (+) x acc) (replicate (n+1) 0) matrix

rowShow matrix = foldr (\x acc -> (unwords x) : acc) [] $ map (\x -> map (\y -> show y) x) matrix

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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

template <typename T>
static inline T ArraySum(vector<T>& A) {
  T res = 0;
  for (auto itr = A.begin(); itr < A.end(); ++itr) res += *itr;
  return res;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

u64 dp[110][100010];

int main() {
  cout << setprecision(18);
  u32 N, W;
  cin >> N >> W;
  vector<pair<u32, u64>> Item(N);
  for (u32 i = 0; i < N; ++i) cin >> Item[i].first >> Item[i].second;
  for (u32 i = 0; i < N; ++i) {
    for (u32 w = 0; w <= W; ++w) {
      if (Item[i].first <= w)
        dp[i + 1][w] =
            max(dp[i][w - Item[i].first] + Item[i].second, dp[i + 1][w]);
      dp[i + 1][w] = max(dp[i + 1][w], dp[i][w]);
    }
  }
  cout << dp[N][W] << endl;
  return 0;
}


Measured memory_bytes: 79360
#include <iostream>
#include <complex>

using namespace std;
typedef complex<double> P;

double cross(P a,P b){
  return a.real()*b.imag()-a.imag()*b.real();
}

int main(){
  int n;
  cin >> n;
  while(n--){
    P p[4];
    for(int i=0; i<4; i++)
      cin >> p[i].real() >> p[i].imag();
    if(cross(p[1]-p[0],p[3]-p[2])==0)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
}

Measured memory_bytes: 1224
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let mut vec: Vec<usize> = vec![];
    for _ in 0..N {
        vec.push(read());
    }
    let mut map: Vec<usize> = vec![0; N + 1];
    let mut max = 0;
    for v in vec {
        map[v] = map[v - 1] + 1;
        max = std::cmp::max(max, map[v]);
    }
    println!("{}", N - max);
}


Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
struct activity
{
	int A, B, C;
};
int vacation(std::vector<activity> arr, int n)
{
	int dp[n + 1][3];
	dp[1][0] = arr[1].A;
	dp[1][1] = arr[1].B;
	dp[1][2] = arr[1].C;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = arr[i].A + max(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i].B + max(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i].C + max(dp[i - 1][0], dp[i - 1][1]);
	}
	return max(dp[n][0], max(dp[n][1], dp[n][2]));
}
int main() {
	int n; cin >> n;
	std::vector<activity> arr(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].A;
		cin >> arr[i].B;
		cin >> arr[i].C;
	}
	cout << vacation(arr, n);

	return 0;
}


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

int main(){
    string str;
    cin >> str;
    //文字列の最後がAGCTのいずれかだと止まらなくなるようなので確実に終わらせるために。
    str += 'Z';
    int ans = 0;

    for(int i = 0; i < str.length();i++){
        int ans1 = 0;
        int j = i;
        while(str.at(j) == 'A' || str.at(j) == 'G' || str.at(j) == 'C' || str.at(j) == 'T'){
            ans1++;
            j++;
            i = j;
        }
        ans = max(ans,ans1);
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <boost/math/common_factor.hpp>
using namespace std;

typedef unsigned long long int ulint;
typedef long long int lint;


map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(){
  lint A, B;
  cin >> A >> B;

  lint c = boost::math::gcd(A, B);

  // cout << "gcd=" << c << endl;
  
  map<int64_t, int> primes = prime_factor(c);

  int64_t count = 0;

  
  
  for (auto it = primes.begin(); it != primes.end(); ++it) {
    ++count;
  }
  // for(int64_t i = 2; i <= c; i++) {
  //   // cout << "i=" << i << ": " << primes[i] << endl;
  //   if (primes[i] > 0) {
  //     ++count;
  //   }
  // }

  cout << count + 1 << endl;

}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int[][] score = new int[10][10];
    int[][] input = new int[h][w];
    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        for (int i=0; i<10; i++) {
            for (int j=0; j<10; j++) {
                score[i][j] = sc.nextInt();
            }
        }

        floyd();

        Map<Integer, Integer> map = new HashMap<>();

        long ans = 0;

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                int tmp = sc.nextInt();
                if (tmp>=0) ans += score[tmp][1];
//                if (map.containsKey(tmp)) {
//                    int val = map.get(tmp);
//                    map.put(tmp, val+1);
//                } else {
//                    map.put(tmp, 1);
//                }
            }
        }

//        System.out.println(map);

//        for (Integer k: map.keySet()) {
//            if (k==-1 || k==0) continue;
//            int val = map.get(k);
//            ans += score[k][1] * val;
//        }


//        for (int i=0; i<10; i++) {
//            for (int j=0; j<9; j++) {
//                System.out.print(score[i][j]+" ");
//            }
//            System.out.println(score[i][9]);
//        }

        System.out.println(ans);

    }

    void floyd() {
        for (int k=0; k<10; k++) {
            start:
            for (int i=0; i<10; i++) {
                if (score[i][k]==0) continue start;
                end:
                for (int j=0; j<10; j++) {
                    if (score[k][j]==0) continue end;
                    if (i==8 && k==4 && j==9) {
//                        System.out.println(score[i][j]);
//                        System.out.println(score[i][k]);
//                        System.out.println(score[k][j]);
                    }

                    score[i][j] = Math.min(score[i][j], score[i][k] + score[k][j]);
                }
            }
        }
    }

}


Measured memory_bytes: 46044
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

int solve()
{
	int res = 0;
	REP( i, 0, 4 )
	{
		int tmp;
		cin >> tmp;
		res += tmp;
	}
	return res;
}

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

	cout << max( solve(), solve() ) << endl;

	return 0;
}

Measured memory_bytes: 1184
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
#define CEIL(A,B) ((A)+(B)-1)/(B)
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k){ll b=1;k=min(n-k,k);DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

string A;
ll c[26];

int main() {
    fastio();
    cin >> A;
    ll N = A.size();
    REP(i, N) c[A[i] - 'a']++;
    ll ans = N * (N - 1) / 2;
    REP(i, 26) ans -= c[i] * (c[i] - 1) / 2;
    cout << ans + 1 << "\n";
	return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

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

  int n, t; cin >> n >> t;
  vec<int, 1> a(n);
  for (auto& i : a) {
    cin >> i;
  }

  int mx = numeric_limits<int>::min();
  for (int i = 1, mn = a[0]; i < n; asMn(mn, a[i]), ++i) {
    asMx(mx, a[i] - mn);
  }

  int ans = 0;
  for (int i = 1, mn = a[0]; i < n; asMn(mn, a[i]), ++i) {
    if (mx == a[i] - mn) {
      ++ans;
    }
  }
  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
const int N = 160;
int f[N][N], n, k, m, g[N<<1][N][N];
#define FOR(i, l, r) for(int i = l; i <= r; ++i)
void mo(int & x) { if(x > m) x -= m; }
void solve1() {
    k /= 2; f[0][0] = 1;
    FOR(i, 1, n) {
        FOR(j, 0, k) mo(f[i][0] += f[i - 1][j]);
        FOR(j, 0, k - 1) mo(f[i][j + 1] += f[i - 1][j]);
    }
    int ans1 = 0, ans2 = 0;
    FOR(i, 0, k) mo(ans1 += f[n / 2][i]);
    FOR(i, 0, k) mo(ans2 += f[(n + 1) / 2][i]);
    int ans = 1ll * ans1 * ans2 % m;
    printf("%d\n", ans);
}
void solve2() {
    g[0][0][0] = 1; int p = 0;
    for(int i = 2; i - k <= n; i += 2) {
        FOR(j, 0, n) 
            FOR(d, 0, k + 1) mo(g[i][0][0] += g[i - 2][j][d]);
        if(i <= n) FOR(j, 0, n) 
            FOR(d, 0, k + 1) mo(g[i][j + 1][0] += g[i - 2][j][d]);
        if(i - k >= 1) FOR(j, 0, n) {
            FOR(d, 1, k) mo(g[i][0][d + 1] += g[i - 2][j][d]);
            mo(g[i][0][0] += g[i - 2][j][0]);
        }
        if(i <= n && i - k >= 1) FOR(j, 0, n)
            for(int d = 0; max(d, j + 1) <= k; ++d)
                mo(g[i][j + 1][max(d + 1, j + 2)] += g[i - 2][j][d]);
        p = i;
    }
    int ans = 0;
    FOR(j, 0, n)
        FOR(d, 0, k + 1) mo(ans += g[p][j][d]);
    printf("%d\n", ans);
}
int main() {
    scanf("%d %d %d", &n, &k, &m);
    if(k & 1) solve2();
    else solve1();
    return 0;
}


Measured memory_bytes: 11192
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<long double,long double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-10;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vl a;

int main(){
	cin>>n;
	a=vl(n);
	for(int i=0;i<n;i++) cin>>a[i];
	ll l=2,r=3;
	for(int i=n-1;i>=0;i--){
		l=((l-1)/a[i]+1)*a[i];
		r=((r-1)/a[i]+1)*a[i];
	}
	if(l==r) cout<<-1<<endl;
	else cout<<l<<' '<<r-1<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
using namespace std;
const int maxn=50+10;
int n,m,cnt;
char a[maxn][maxn];
struct node{
	int x,y,step;
};
bool vis[maxn][maxn];
int xx[5]={0,1,0,-1,0};
int yy[5]={0,0,1,0,-1};
int bfs(){
	queue<node>q;
	q.push({1,1,1});
	vis[1][1]=1;
	while(!q.empty()){
		node tmp=q.front();
		q.pop();
		if(tmp.x==n && tmp.y==m)
			return tmp.step;
		REP(i,1,4){
			int x2=tmp.x+xx[i],y2=tmp.y+yy[i];
			if(vis[x2][y2]==1)continue;
			if(a[x2][y2]=='#')continue;
			if(x2<1 || x2>n)continue;
			if(y2<1 || y2>m)continue;
			vis[x2][y2]=1;
			q.push({x2,y2,tmp.step+1});
		}
	}
	return -1;
}
int main(){
	scanf("%d%d",&n,&m);
	REP(i,1,n)scanf("%s",a[i]+1);
	REP(i,1,n)REP(j,1,m)
		cnt+=a[i][j]=='#' ? 1 : 0;
	int ans=bfs();
	if(ans==-1)cout<<-1<<endl;
	else cout<<n*m-ans-cnt<<endl;
	return 0;
}



Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

int[][] warshallFloyd(int n, int[][] adj) {
    auto d = new int[][](n + 1, n + 1);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            d[i][j] = adj[i][j] == 0 ? int.max / 10 : adj[i][j];
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    return d;
}

int calc(int[] rs, int n, int[][] adj) {
    auto costs = warshallFloyd(n, adj);

    sort(rs);
    int ans = int.max;
    foreach (xs; rs.permutations) {
        int cost = 0;
        for (int i = 0; i < xs.length - 1; i++) {
            cost += costs[xs[i]][xs[i + 1]];
        }

        ans = min(ans, cost);
    }
    return ans;
}

void main() {
    auto nmr = readints;
    int n = nmr[0], m = nmr[1];
    auto rs = readints;

    auto adj = new int[][](n + 1, n + 1);
    for (int i = 0; i < m; i++) {
        auto abc = readints;
        int a = abc[0], b = abc[1], c = abc[2];
        adj[a][b] = adj[b][a] = c;
    }

    auto ans = calc(rs, n, adj);
    writeln(ans);
}


Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
long long a[20000];
long long d[20000];
long long c[20000];
int main()
{
    int n;
    cin>>n;
    long long  sum=1000;
    long long  k=0;
    int x=0,y=0;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i]>=a[i+1]&&a[i]>a[i-1])
        {
            d[x++]=i;
        }
    }
    a[0]=2e9;
    a[n+1]=2e9;
    for(int i=1; i<=n; i++)
    {
        if(a[i]<a[i+1]&&a[i]<=a[i-1])
        {
            c[y++]=i;
        }
    }
    for(int i=0,j=0;i<y;i++)
    {
        for(;j<x;j++)
        {
            if(d[j]>c[i]&&a[c[i]]<a[d[j]])
            {
                k=k+sum/a[c[i]];
                sum=sum%a[c[i]];
                sum+=k*a[d[j]];
                k=0;
                break;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3596
//BadWaper gg
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int x=read();
	cout<<(1000-x%1000)%1000<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;

Node treeMinimum(Node );
Node treeSearch(Node , int );
Node treeSuccessor(Node );
void insert(int );
void inorder(Node );
void preorder(Node );
void treeDelete(Node );
void Transplant(Node, Node);


int main(void){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL )
	printf("yes\n");
      else
	printf("no\n");
    }
    
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}
 
Node treeMinimum(Node x){
 
  while(x->left != NIL)
    x = x->left;
 
  return x;
   
}

Node treeSearch(Node u, int k){
  //ノードの中身が空の場合、
  if(u == NIL || k == u->key)
    return u;
   
  if(k < u->key)
    return treeSearch(u->left, k);
   
  else
    return treeSearch(u->right, k);
   
}

Node treeSuccessor(Node x){
   
  Node y;
 
  if(x->right != NIL)
    return treeMinimum(x->right);
 
  y = x->parent;
 
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
 
  return y;
 
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x != NIL){
    y = x;
    if(z->key < x->key)
      x = x->left;
 
    else
      x = x->right;
  }
   
  z->parent = y;
 
  if(y == NIL)
    root = z;
 
  else if(z->key < y->key)
    y->left = z;
 
  else
    y->right = z;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  //Node x; // child of y
  if(z->left == NIL)
    Transplant(z, z->right);

  else if(z->right == NIL)
    Transplant(z, z->left);

  else{
    y = treeMinimum(z->right);
    if(y->parent != z){
      Transplant(y, y->right);
      y->right = z->right;
      y->right->parent = y;
    }

    Transplant(z,y);
    y->left = z->left;
    y->left->parent = y;
  }
}

void Transplant(Node u, Node v){
  if(u->parent == NIL)
    root = v;

  else if(u == u->parent->left)
    u->parent->left = v;

  else
    u->parent->right = v;

  if(v != NIL)
    v->parent = u->parent;
}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}

void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}

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

using namespace std;

int diff(int a, int b) {
    if (a < b) return b - a;
    return a - b;
}

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    cout << max(diff(a, b) - w, 0) << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e18;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int N=200005;

void solve()
{
int d,t,s;
cin>>d>>t>>s;
if(s*t>=d)
{
    cout<<"Yes"<<endl;
}
else
{
    cout<<"No"<<endl;
}



}

int32_t main()
{
   IOS;
    int t;
    t=1;
    //cin>>t;
    
    while(t--)
    {
       
        
        solve();
    }
    return 0;
}






Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

template<typename Monoid,typename F>
class SegmentTree{
private:
    int sz;
    vector<Monoid> seg;
    const F op;
    const Monoid e;
public:
    SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){
        sz = 1;
        while(sz<=n) sz <<= 1;
        seg.assign(2*sz,e);
    }
    void set(int k, const Monoid &x){
        seg[k+sz] = x;
    }
    void build(){
        for(int i=sz-1;i>0;i--){
            seg[i] = op(seg[2*i],seg[2*i+1]);
        }
    }
    void update(int k,const Monoid &x){
        k += sz;
        seg[k] += x;
        while(k>>=1){
            seg[k] = op(seg[2*k],seg[2*k+1]);
        }
    }
    Monoid query(int l,int r){
        Monoid L = e,R = e;
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1) L = op(L,seg[l++]);
            if(r&1) R = op(seg[--r],R);
        }
        return op(L,R);
    }
    Monoid operator[](const int &k)const{
        return seg[k+sz];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;
    vvec<int> Llist(M+1);
    for(int i=0;i<N;i++){
        int l,r;
        cin >> l >> r;
        Llist[l].push_back(r);
    }
    vec<int> ans(M+1);
    struct query{
        int r,d;
    };
    vvec<query> Q(M+2);
    for(int d=1;d<=M;d++){
        for(int l=0;l<=M;l+=d){
            int r = l+d;
            if(r>M) r = M+1;
            Q[l].push_back({r,d});
        }
    }
    auto op = [](int a,int b){return a+b;};
    SegmentTree<int,decltype(op)> seg(M+2,op,0);
    for(int l=M;l>=0;l--){
        for(auto& q:Q[l]){
            ans[q.d] += seg.query(0,q.r);
        }
        for(auto& r:Llist[l]) seg.update(r,1);
    }
    for(int i=1;i<=M;i++) cout << N-ans[i] << "\n";
}

Measured memory_bytes: 23924
h,w = map(int, input().split())
k = [list(input()) for i in range(h)]

ans = True
for i in range(1,h-2):
    for j in range(1,w-2):
        if k[i][j] == "#" and k[i-1][j] =="." and k[i][j-1] =="." and k[i+1][j] =="." and k[i][j+1] =="." :
            ans = False

if ans:
    print('Yes')

else:
    print('No')

Measured memory_bytes: 3064
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  lint n,k;
  cin>>n>>k;
  vector<lint> h(n);
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  std::sort(h.begin(), h.end(), std::greater<>());
  lint result=0;
  for(int i=k;i<n;i++){
    result+=h[i];
  }
  cout<<result<<endl;


  return 0;
}




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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  bool is_even = true;

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

  int ans=0;
  while(is_even){
    for (int i = 0; i < n; i++)
    {
      a[i]/=2;
      if(a[i]%2==1) is_even=false;
    }
    ans++;    
  }

  cout << ans << endl;
}

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

#define pii pair<int,int>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define PH push
#define ll long long

const int MOD=1e9+7;

int n;
int a[500100];
long long sum1[500100],sum2[500100];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		sum1[i]=sum1[i-1]+abs(a[i-1]-a[i]);
		sum2[n-i+1]=sum2[n-i+2]+abs(a[n-i+1]-a[n-i+2]);
	}
	for(int i=1;i<=n;i++)
		printf("%I64d\n",sum1[i-1]+abs(a[i-1]-a[i+1])+sum2[i+1]);
	return 0;
}


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

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

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let mut c = vec![0; n + 1];
    for _ in 0..n {
        let a: usize = scan(tokens);
        c[a] += 1;
    }
    let mut d = vec![0; n + 1];
    for i in 0..n + 1 {
        d[c[i]] += 1;
    }
    let mut cumsum0 = vec![0; n + 1];
    let mut cumsum1 = vec![0; n + 1];
    for i in 1..n + 1 {
        cumsum0[i] = cumsum0[i - 1] + d[i];
        cumsum1[i] = cumsum1[i - 1] + d[i] * i;
    }
    let mut i = n;
    for k in 1..n + 1 {
        while i > 0 && (cumsum1[i] + (cumsum0[n] - cumsum0[i]) * i) / i < k {
            i -= 1;
        }
        println!("{}", i);
    }
}


Measured memory_bytes: 23420
def add(lis,check_list):
    for index in range(len(lis)):
        if lis[index][0]==check_list[0]:
            lis[index][1]+=int(check_list[1])*int(check_list[2])
            return
    lis.append([check_list[0],int(check_list[1])*int(check_list[2])])

while True:
    num=int(raw_input())
    if num==0: break
    lis=[]
    for i in range(num):
        l=raw_input().split(" ")
        add(lis,l)
    c=0
    for ele in lis:
        if ele[1]>=1000000:
            print ele[0]
            c+=1
    if c==0: print "NA"

Measured memory_bytes: 4392
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[2100];
int dp[2100][2100];
int dp2[2100][2100];
int K;
int v[2100];
void calc(int a,int b){
	v[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		calc(g[a][i],a);
		v[a]+=v[g[a][i]];
	}
	for(int i=0;i<=g[a].size();i++)for(int j=0;j<=K;j++)dp2[i][j]=-999999;
	dp2[0][0]=1;
	int sz=0;
	int at=0;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		for(int j=0;j<=sz;j++){
			dp2[at+1][j]=max(dp2[at+1][j],dp2[at][j]);
			for(int k=0;j+k+1<=K;k++){
				dp2[at+1][max(j,k+1)]=max(dp2[at+1][max(j,k+1)],dp2[at][j]+dp[g[a][i]][k]);
			}
		}
		at++;
		sz+=v[g[a][i]];
	}
	for(int i=0;i<=K;i++)dp[a][i]=dp2[at][i];
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	K=b;
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	calc(0,-1);
	int ret=0;
	for(int i=0;i<a;i++)for(int j=0;j<=b;j++)
		ret=max(ret,dp[i][j]);
	printf("%d\n",a-ret);
}

Measured memory_bytes: 22528