akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int N=2005,mod=1000000007;
int n,k,dp[N][N],fac[N*N],ifac[N*N];
int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)r=1ll*r*a%mod;return r;}
int C(int a,int b){return a<0||b<0||a<b?0:1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
int main()
{
	for(int i=fac[0]=1;i<N*N;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N*N-1]=pw(fac[N*N-1],mod-2);
	for(int i=N*N-1;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
	scanf("%d%d",&n,&k);
	if(k==1){puts("1");return 0;}
	dp[0][0]=1;
	for(int i=0;i<=n;i++)for(int j=0;j<=i;j++)
	{
		if(i)dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
		if(j)dp[i][j]=(dp[i][j]+1ll*dp[i][j-1]*C(n*k-i-(j-1)*(k-1)-1,k-2))%mod;
	}
	printf("%d\n",1ll*dp[n][n]*fac[n]%mod);
	return 0;
}

Measured memory_bytes: 47360
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

int main() {
    int n;
    cin >> n;
    vi s(n);
    int ans = 0;
    rep(i, n) {
        cin >> s[i];
        ans += s[i];
    }
    sort(all(s));
    
    if(ans % 10 != 0) {
        cout << ans << endl;
        return 0;
    }

    rep(i, n) {
        if(s[i] % 10 != 0) {
            cout << ans - s[i] << endl;
            return 0;
        } 
    }

    cout << 0 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    if(a + w < b) cout << b - a - w << endl;
    else if(b + w < a) cout << a - b - w << endl;
    else cout << 0 << endl;
    
}

Measured memory_bytes: 256
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ll long long
using namespace std;



int main() {

    string C;

    cin >> C;

    if(C == "a"){
        cout << "b" <<endl;
    }else if(C == "b"){
        cout << "c" <<endl;
    }else if(C == "c"){
        cout << "d" <<endl;
    }else if(C == "d"){
        cout << "e" <<endl;
    }else if(C == "e"){
        cout << "f" <<endl;
    }else if(C == "f"){
        cout << "g" <<endl;
    }else if(C == "g"){
        cout << "h" <<endl;
    }else if(C == "h"){
        cout << "i" <<endl;
    }else if(C == "i"){
        cout << "j" <<endl;
    }else if(C == "j"){
        cout << "k" <<endl;
    }else if(C == "k"){
        cout << "l" <<endl;
    }else if(C == "l"){
        cout << "m" <<endl;
    }else if(C == "m"){
        cout << "n" <<endl;
    }else if(C == "n"){
        cout << "o" <<endl;
    }else if(C == "o"){
        cout << "p" <<endl;
    }else if(C == "p"){
        cout << "q" <<endl;
    }else if(C == "q"){
        cout << "r" <<endl;
    }else if(C == "r"){
        cout << "s" <<endl;
    }else if(C == "s"){
        cout << "t" <<endl;
    }else if(C == "t"){
        cout << "u" <<endl;
    }else if(C == "u"){
        cout << "v" <<endl;
    }else if(C == "v"){
        cout << "w" <<endl;
    }else if(C == "w"){
        cout << "x" <<endl;
    }else if(C == "x"){
        cout << "y" <<endl;
    }else if(C == "y"){
        cout << "z" <<endl;
    }

    return 0;


}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const int mod=1000000007;
const int mod2=998244353;

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

ll yakusu(ll N){
    ll y=1;
    for(ll i=2;i*i<=N;i++){
        if(N%i==0)y=i;
    }
    return y;
}
int main()
{
	ll N;cin>>N;
    ll a=yakusu(N);
    cout<<(a-1)+(N/a-1)<<endl;
}

 
    

Measured memory_bytes: 256
import sys
N=int(input())
if N==2:
    print(1)
    sys.exit()
if N==3:
    print(4)
    sys.exit()
mod=10**9+7
table=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
#print(table,rtable)
ans=0
l=0
for k in range(N):
    if 0>2*k-N:
        continue
    num=table[k]*table[N-1-k]
    div=table[k-1]*rtable[N-1-k]*rtable[k-1-(N-1-k)]
    div%=mod
    num*=div
    num%=mod
    ans+=k*(num-l)
    l=num
    l%=mod
    ans%=mod
    #print(k, num, div)
print(ans)

Measured memory_bytes: 56284
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    int menu[n];
    for(int i=0;i<n;i++){
      cin>>menu[i];
    }
    sort(menu,menu+n);
    int p = -1;
    bool money[x+1];
    money[0] = true;
    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]]){
	  money[i] = true;
	  break;
	}
      }
      if(money[i]&&prime[i])p=i;
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

Measured memory_bytes: 2820
#include <stdio.h>
#include <stdlib.h>
int a[100000][2] = {};
int cmpint(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}
int main() {
	int n, m, sum = 0, r = 0;
	long long ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i][0], &a[i][1]);
	}
	qsort(a, n, sizeof(a[0]), cmpint);
	r = m;
	for (int i = 0;; i++) {
		if (sum + a[i][1] >= m) {
			ans += (long long)a[i][0] * r;
			break;
		}
		ans += (long long)a[i][0] * a[i][1];
		sum += a[i][1];
		r -= a[i][1];
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1788
let ans, p = ref 0, ref 0
let _ = Scanf.scanf "%d %d %d" @@ fun n a b -> for i = 1 to n do Scanf.scanf " %d" @@ fun x -> if i > 1 then ans := !ans + min b (a * (x - !p)); p := x done; Printf.printf "%d\n" !ans

Measured memory_bytes: 2688
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int>A(3*n);
  for(int i=0;i<3*n;i++){
    cin>>A[i];
  }
  sort(A.begin(),A.end(),greater<int>());
  ll ans=0;
  for(int i=1;i<2*n;i+=2){
    ans+=(ll)A[i];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1408
using System;
    using System.Linq;
    using System.Collections.Generic;
     
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] inputStr = Console.ReadLine().Split(' ');
            int len = inputStr.Length;
            long[] A = new long[len];
            for(int i=0; i<len; i++){
                A[i] = long.Parse(inputStr[i]);
            }
     
            /*
            bool sorted = false;
            int x;
            while(!sorted){
                sorted = true;
                for(int i=0; i<len-1; i++){
                    if(input[i]<input[i+1]){
                        x = input[i];
                        input[i] = input[i+1];
                        input[i+1] = x;
     
                        sorted = false;
                    }
                }
            }
            */
     
            Array.Sort(A);
            Array.Reverse(A);
     
            long[] edges = {0,0};
            int j = 0;
            for(int i=0; i<len-1; i++){
                if(A[i]==A[i+1]){
                    edges[j] = A[i];
                    j++;
                    i++;
                }
                if(j==2) break;
            }
     
            Console.WriteLine(edges[0]*edges[1]);
        }
    }

Measured memory_bytes: 19040
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    boolean ju[] = new boolean[100001];
    int pe[] = new int[100001];
    
    for(int i = 0 ; i < m ; ++i){
      int no = sc.nextInt();
      String res = sc.next();
      no--;
      
      if(res.equals("WA") && ju[no] != true){
        pe[no]++;
      }
      if(res.equals("AC")){
        ju[no] = true;
      }
      
    }
    
    int ac = 0;
    int wa = 0;
    
    for(int i = 0 ; i < n ; ++i){
      if(ju[i]){
        ac++;
        wa += pe[i];
      }
      
    }
    
    System.out.println(ac + " " + wa);
    
  }
}

Measured memory_bytes: 60224
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
map <int,int> mp;
vector<int> V;
#define debug(x) cerr << #x << ": " << x << "\n";
#define INF (1<<29) //53687091
#define INFLL (1ll<<58)
#define EPS (1e-10)
static const int MAX=(int) 1e6;
static const int MOD=(int) 1e9+7;
static const int NMAX=50;
static const int MMAX=50;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };

struct node{
    int x,y,id;
}a[MAX];
struct edge{
    int u,v,wt;
    bool operator < (const edge &e) const{
        return wt<e.wt; //重みが昇順になるように
    }
}g[MAX];

bool cmpx(node a,node b) { return a.x < b.x; }
bool cmpy(node a,node b) { return a.y < b.y; }

//-------------UnionFind--------------------
int par[MAX]; //親
int un_rank[MAX]; //木の深さ
void init(int n){
    for(int i = 0; i < n; i++){
        par[i] = i; un_rank[i] = 0;
    }
}
int find(int x){
    //xが木の根ならそれを、そうでないなら根を記録しながら木の根を返す
    return x==par[x] ? x : par[x] = find(par[x]);
}
bool same(int x,int y){
    //xとyが同じ集合に属するか
    return find(x) == find(y);
}
//xとyの属する集合を併合
void unite(int x, int y){
    x = find(x); y = find(y);
    if(x == y) return;
    
    if(un_rank[x] < un_rank[y]){
        par[x] = y;
        //united[y] += united[x];
    }else{
        par[y] = x;
        //united[x] += united[y];
        if(un_rank[x] == un_rank[y]) un_rank[x]++;
    }
}
//------------------------------------------


int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    
    int N,m = 0;
    ll res = 0ll;
    cin >> N;
    
    for(int i=0;i<N;i++){
        par[i]=i;
        cin >> a[i].x >> a[i].y;
        a[i].id = i;
    }
    
    sort(a,a+N,cmpx); //x座標でソート
    for(int i=0;i<N-1;i++) g[m++] = (edge){a[i].id, a[i+1].id, a[i+1].x-a[i].x};
    sort(a,a+N,cmpy);
    for(int i=0;i<N-1;i++) g[m++] = (edge){a[i].id, a[i+1].id, a[i+1].y-a[i].y};
    sort(g,g+m);
    
    for(int i=0;i<m;i++){
        if(!same(g[i].u,g[i].v)){ //g[i]をつないでも閉路ができない
            res += g[i].wt; //コストを加算
            unite(g[i].u,g[i].v);
        }
    }
    
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 12928
#include"bits/stdc++.h"
using namespace std;
bool f[200001];
int main(){
	vector<int> vec;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int t;
		cin>>t;
		vec.push_back(t);
	}
	int cnt=0;
	for(int i=vec.size()-1;i>=0;i-=2){
		cout<<vec[i]<<" ";
		f[i]++;
		cnt++;
	}
	for(int i=0;i<vec.size();i++){
		if(!f[i]){
			cnt++;
			cout<<vec[i]<<(cnt==vec.size()?"\n":" ");
		}
	}
	return 0;
}

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    string k;   cin >> k;
    ll l_k = k.length();
    int d;  cin >> d;
    vector<vector<vector<ll> > > dp(k.length()+1, vector<vector<ll> >(2, vector<ll>(d, 0)));
    ll mod = 1e9+7;

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

    for (int i = 0; i < l_k; i++) {
        for (int j = 0; j < d; j++) {
            for (int f = 0; f < 2; f++) {
                for (int l = 0; l < 10; l++) {
                    if (f || l < k[i]-'0')
                        dp[i+1][1][(j+l)%d] = (dp[i+1][1][(j+l)%d]+dp[i][f][j])%mod;
                    else if (l == k[i]-'0')
                        dp[i+1][0][(j+l)%d] = (dp[i+1][0][(j+l)%d]+dp[i][f][j])%mod;
                }
            }
        }
    }

    cout << (dp[l_k][1][0] + dp[l_k][0][0]-1+mod)%mod << endl;
    return 0;
}

Measured memory_bytes: 20136
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	n, k := getInt(), getInt()
	s := []rune(getString())

	cnt := 0
	sum := 0
	now := ' '
	for i, r := range s {
		if r != now {
			now = r
			sum += cnt
			cnt = 0
		} else {
			cnt++
			if i == n-1 {
				sum += cnt
			}
		}
	}

	ans := min(n-1, sum+(2*k))
	fmt.Fprintln(wr, ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// -----------------------------------------

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	buf := 200001
	sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 1280
import math

def readinput():
    n=int(input())
    h=list(map(int,input().split()))
    return n,h

def printParent(i,h):
    parent=math.floor(i/2)
    if(parent>0):
        print('parent key = {}, '.format(h[parent]),end='')

def printLeft(i,h):
    left=2*i
    if(left<=len(h[1:])):
        print('left key = {}, '.format(h[left]),end='')

def printRight(i,h):
    right=2*i+1
    if(right<=len(h[1:])):
        print('right key = {}, '.format(h[right]),end='')

def main(n,h):
    h.insert(0,-1)
    for i in range(1,n+1):
        print('node {}: key = {}, '.format(i, h[i]),end='')
        printParent(i,h)
        printLeft(i,h)
        printRight(i,h)
        print('')

    return

if __name__=='__main__':
    n,h=readinput()
    main(n,h)


Measured memory_bytes: 5780
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
  ll a,b,c;
  cin>>a>>b>>c;
  if(a*b>c)
    cout<<c;
  if(a*b<c)
    cout<<a*b;
  if(a*b==c)
    cout<<c;
}
  

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

using namespace std;

typedef long long ll;

const int maxn = 111;

bool buf;
int n, m;
int a[maxn];

int main() {

	buf = scanf("%d %d", &n, &m);

	int o = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%d", a+i);
		o += (int)(a[i]&1);
		if (a[i]&1) {
			if (o == 1)
				swap(a[i], a[1]);
			else if (o == 2)
				swap(a[i], a[m]), i--, m--;
			else {
				puts("Impossible"); 
				return 0;
			}
		}
	}
	m += (o==2);

	for (int i = 1; i <= m; i++) {
		printf("%d%c", a[i], (i == m ? '\n' : ' '));
	}

	if (m == 1) {
		if (n == 1) puts("1\n1");
		else printf("2\n%d 1\n", n-1);
		return 0;
	}

	printf("%d\n%d ", m - (int)(a[m]==1), a[1]+1);
	for (int i = 2; i < m; i++) {
		printf("%d ", a[i]);
	}
	if (a[m] != 1)
		printf("%d", a[m]-1);
	putchar('\n');

	return 0;
}

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

#define      ll      long long int

const int N = 3005;
ll ara[N];
ll n;

ll val(ll x)
{
    ll s = 0, i;
    for (i = 1; i <= n; i++) {
        s += (x % ara[i]);
    }
    return s;
}

int main( )
{
    ll s = 0, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> ara[i];
        s += (ara[i] - 1);
    }
    cout << s << '\n';
    return 0;
}

Measured memory_bytes: 384
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int x = sc.nextInt();
		int y = sc.nextInt();

		// 計算
		String result = "No";
		for(int i = 0; i <= x; i++){
		    if(i*2 + (x-i)*4 == y) result = "Yes";
		}
		
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 25388
n, m = map(int, input().split())
h = list(map(int, input().split()))

good = [1] * n
for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] > h[b-1]:
        good[b-1] = 0
    elif h[b-1] > h[a-1]:
        good[a-1] = 0
    else:
        good[a-1] = 0
        good[b-1] = 0
print(sum(good))


Measured memory_bytes: 20112
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_v<T>(ts...)); }
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }

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

	vector<pair<int, int>> ans;
	if (N % 2) {
		rep(i, 0, N - 1) {
			ans.emplace_back(i + 1, N);
		}
		rep(i, 0, N - 1) {
			rep(j, i + 1, N - 1) {
				if (j + 1 == N - 1 - i)continue;
				ans.emplace_back(i + 1, j + 1);
			}
		}
	}
	else {
		rep(i, 0, N) {
			rep(j, i + 1, N) {
				if (j + 1 == N - i)continue;
				ans.emplace_back(i + 1, j + 1);
			}
		}
	}

	cout << ans.size() << endl;

	rep(i, 0, ans.size()) {
		cout << ans[i].first << " " << ans[i].second << endl;
	}


	return 0;
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
#include <vector>
#include <utility>
#define ll long long
#define loop(i,s,e) for(ll i=s;i<e;i++)
#define max(x,y) (x>y?x:y)
#define min(x,y) (x>y?y:x)

ll maxValue(ll *wt, ll * vl, ll **dp, int n, ll w){
    if(w<=0||n<0)return 0;

    if(dp[n][w]!=-1)return dp[n][w];

    if(wt[n]>w)dp[n][w]= maxValue(wt,vl,dp,n-1,w);
    else{
        dp[n][w]=max(maxValue(wt,vl,dp,n-1,w-wt[n])+vl[n],maxValue(wt,vl,dp,n-1,w));
    }     
    return dp[n][w];
}


int main(){
    int n;cin>>n;
    ll w;cin>>w;
    ll *weights=new ll [n];
    ll *values=new ll [n];
    ll **dp=new ll*[n];
    loop(i,0,n){
        cin>>weights[i]>>values[i];
        dp[i]=new ll [w+1];
        loop(j,0,w+1)dp[i][j]=-1;
    }
    cout<<maxValue(weights,values,dp,n-1,w)<<endl;
}

Measured memory_bytes: 78720
using System;
using System.Diagnostics;
using System.IO;

namespace AtCoder.ABC113 {
    class B {
        static void Main() => CustomMain();

        static void Solve() {
            var n = ReadInt();
            int t, a;
            ReadMulti(out t, out a);
            var h = ReadIntArray();

            var ans = 1;
            var nearA = t - h[0] * 0.006;
            for (int i = 1; i < n; i++) {
                var temp = t - h[i] * 0.006;
                if (Math.Abs(a - nearA) > Math.Abs(a - temp)) {
                    nearA = temp;
                    ans = i + 1;
                }
            }

            WriteAnswer(ans);
        }

        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11292
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#pragma clang diagnostic ignored "-Wdeprecated-declarations"
#define _CRT_SECURE_NO_WARNINGS
#endif
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x) {x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void print(T n) {register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);pc(10);}
template<typename First, typename ... Ints>
void scan(First &arg, Ints&... rest) { scan(arg);scan(rest...); }

using namespace std;
const int MM = 1e5+2;

int N, M, dp[MM];
vector<int> adj[MM];

int go(int n){
    if(adj[n].empty())
        return dp[n] = 0;
    
    if(dp[n] != -1)
        return dp[n];
    
    int ret = 0;
    for(int u: adj[n])
        ret = max(ret, go(u));
    
    return dp[n] = ret+1;
}

int main(){
    
    memset(dp, -1, sizeof dp);
    
    scan(N, M);
    
    for(int i = 0,a,b; i < M; i++){
        scan(a, b);
        adj[a].push_back(b);
    }
    
    int ans = 0;
    for(int i = 1; i <= N; i++){
        ans = max(ans, go(i));
    }
    print(ans);
    
    return 0;
}

Measured memory_bytes: 8192
t = str(input())
s=0
k=0
for i in range(0,len(t),2):
  if(t[i]=='L'):
    s=1
for i in range(1,len(t),2):
  if(t[i]=='R'):
    k=1
if(s==1):
  print('No')
elif(k==1):
  print('No')
else:
  print('Yes')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define watch(x) cout<<(#x)<<" is "<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define pq priority_queue
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using pss=pair<string,string>;
using graph=vector<vector<int>>;
using wgraph=vector<vector<pll>>;


const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int ex[8]={1,1,0,-1,-1,-1,0,1};
const int ey[8]={0,1,1,1,0,-1,-1,-1};
const ld E=1e-10;

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    if(ret>=p)ret%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b=10){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

int bis(vector<int> v,int key){
  int left=-1,right=v.size();
  while(abs1(right-left)>1){
    int mid=left+(right-left)/2;
    if(v[mid]<=key)left=mid;
    else right=mid;
  }
  return left;
}

int main(){
  int i,j,k,cnt=0;
  int n;
  cin>>n;
  vector<pll> a(n),b(n);
  for(i=0;i<n;i++){
    cin>>a[i].se>>a[i].fi;
  }
  for(i=0;i<n;i++){
    cin>>b[i].fi>>b[i].se;
  }
  sort(all(a),greater<pll>());
  sort(all(b));
  for(i=0;i<n;i++){
    swap(a[i].fi,a[i].se);
  }
  for(i=0;i<n;i++){
    for(j=0;j<a.size();j++){
      if(a[j].fi<b[i].fi && a[j].se<b[i].se){
        cnt++;
        a.erase(a.begin()+j);
        break;
      }
    }
  }
  cout<<cnt<<endl;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    vector<int> A(2);
    cin >> A[0] >> A[1];
    rep(i, 3) {
        int ans = i + 1;
        if (ans == A[0] || ans == A[1]) continue;
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<LP> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;

struct perm {
private:
	int sz;
	vector<ll> p, invp;
public:
	perm(int n) {
		sz = n + 1;
		p.resize(sz), invp.resize(sz);
		p[0] = 1;
		rep1(i, sz - 1) {
			p[i] = p[i - 1] * i%mod;
		}
		invp[sz - 1] = 1;
		ll cop = mod - 2, x = p[sz - 1];
		while (cop) {
			if (cop % 2)invp[sz - 1] = invp[sz - 1] * x%mod;
			cop >>= 1; x = x * x % mod;
		}
		per(i, sz - 1) {
			invp[i] = invp[i + 1] * (i + 1) % mod;
		}
	}
	ll comb(ll x, ll y) {
		if (x < y || y < 0)return 0;
		ll ret = p[x];
		(ret *= invp[y]) %= mod;
		(ret *= invp[x - y]) %= mod;
		return ret;
	}
	ll combP(ll x, ll y) {
		if (x < y || y < 0)return 0;
		return p[x] * invp[x - y] % mod;
	}
};
perm p(1 << 23);

void solve() {
	ll ans = 0;
	int n, m; cin >> n >> m;
	ans = p.comb(3 * m + n - 1, 3 * m);
	for (int i = 2 * m + 1; i <= 3 * m; i++) {
		ll dif = 3 * m - i;
		ll dec = (ll)n * p.comb(dif + n - 1 - 1, dif) % mod;
		ans -= dec;
		ans = (ans%mod + mod) % mod;
	}
	for (int i = m + 2; i <= n; i += 2) {
		ll t = p.comb(n, i);
		ll rest = (3 * m - i) / 2;
		ll z = p.comb(rest + n - 1, rest);
		ll dec = t * z%mod;
		ans -= dec;
		ans = (ans%mod + mod) % mod;
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
	//stop
	return 0;
}


Measured memory_bytes: 131328
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=110,P=1e9+7;
inline int read(){
	int x=0,f=0,c=getchar();
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+c-'0';return f?-x:x;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);putchar(x%10+'0');
}
int n,m,a[N],f[N][N][N],ans;
inline void A(int&x,int y){(x+=y)%=P;}
int main(){
	//freopen("1.out","w",stdout);
	register int i,l,r,j,k,t;
	n=read();m=n+n-1;
	for(i=m;i;i--)a[i]=read();
	sort(a+1,a+m+1);
	f[n][0][0]=1;
	for(i=n;i>1;i--){
		l=(a[i]!=a[i-1]);r=(a[m-i+1]!=a[m-i+2]);
		for(j=n+n-i-i;j>=0;j--)for(k=n+n-i-i;k>=0;k--)
		if(f[i][j][k]){
			A(f[i-1][j+l][k+r],f[i][j][k]);
			for(t=0;t<j+l;t++)A(f[i-1][t][k+r+1],f[i][j][k]);
			for(t=0;t<k+r;t++)A(f[i-1][j+l+1][t],f[i][j][k]);
		}
	}
	for(j=0;j<=m;j++)for(k=0;k<=m;k++)A(ans,f[1][j][k]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3456
#include <iostream>
#include <math.h>
#include <string> 
using namespace std;
#define MAX 200000

int main(){
    int n;
    unsigned long long int a[2]={2,1},ans;
    cin>>n;
    if(n==1)ans=1;
    else if(n==0)ans=2;
    else {
        while(--n>0){            
            ans=a[0]+a[1];
            a[0]=a[1];
            a[1]=ans;
        }        
    }
    cout<<ans<<endl;
    return 0;    
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;

int main()
{
	int32_t H, W;
	cin >> H >> W;

	vector<string> C(H);
	for (int32_t h = 0; h < H; h++)
		cin >> C[h];

	for (int32_t h = 0; h < H * 2; h++)
		cout << C[h / 2] << endl;

	return 0;
}

Measured memory_bytes: 256
a,b=map(int,input().split())
cand_b=[b*10 + i for i in range(10*b)]
def ans(cand):
  for price in cand:
    if int(price*0.08)==a and int(price*0.1)==b:
      print(price)
      return
  print(-1)

ans(cand_b)

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];

    vector<int> t(200000, 0);
    for (int i=0; i<n; i++) t[a[i]]++;
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    int c = 0;
    int cnt = 0;
    while(k > c) {
        cnt += t[c];
        c++;
    }
    cout << n - cnt << endl;

    return 0;
}


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

int main() {
	// your code goes here
	//0段目...まだ踏み出してない
	//1段目...１通りなのは明らか
	//2段目...1x2か2段でくる
	int n[31]={1,1,2};
	//3段目は0,1,2段目から来る
	//同様に、i段目はi-1,i-2,i-3段目から来る
	for(int i=3;i<=31;i++)n[i]=n[i-1]+n[i-2]+n[i-3];
	int n_steps;
	while(cin>>n_steps, n_steps){
		cout<<n[n_steps]/10/365+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>

long euclid(long x,long y){
  long s;
  s = x % y;
  if(s !=0)
    euclid(y,s);
  else
    return y;
}

int main(){
  long a,b,x;
  while(scanf("%ld %ld",&a,&b)!=-1){
    if(a<b){
      x=a; a=b; b=x;
    }
    x=euclid(a,b);
    
    printf("%ld %ld\n",x,a*(b/x));
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;



void solve(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n, m;
    cin >> n >> m;

    vector<pair<ll, ll>> vp(n);
    rep(i, 0, n) cin >> vp[i].first >> vp[i].second;

    sort(ALL(vp));

    ll ans = 0;
    rep(i, 0, n){
        if(m > vp[i].second){
            m -= vp[i].second;
            ans += vp[i].first * vp[i].second;
        }else{
            ans += vp[i].first * m;
            break;
        }
    }

    cout << ans << "\n";
}


int main() {
    solve();
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <bitset>
using namespace std;

#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define repm(i, a, n) for (ll i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<vector<int>>
#define vll vector<ll>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()
#define sort_v(a) sort(a.begin(), a.end())
#define reverse_v(a) reverse(a.begin(), a.end())

void print(bool c)
{
    (c) ? (cout << "Yes" << endl) : (cout << "No" << endl);
}

void Print(bool c)
{
    (c) ? (cout << "YES" << endl) : (cout << "NO" << endl);
}

//最小公倍数
template <typename T>
T gcd(T a, T b)
{
    while (1)
    {
        if (a < b)
            swap(a, b);
        if (b == 0)
            break;
        a %= b;
    }
    return a;
}

//最大公約数
template <typename T>
T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}
//セカンドキー->ファーストキーの順ソート
bool cmp(const pii &a, const pii &b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

//右下左上
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

int eve(int x)
{
    if (x % 400 == 0)
        return 1;
    if (x % 100 == 0)
        return 0;
    if (x % 4 == 0)
        return 1;
    return 0;
}

ll h, w;
vllll pass(50, vll(50));
vs s(50);
struct P
{
    int y, x, c;
} p;
queue<P> q;

ll bfs()
{
    if (q.empty())
        return -1;
    p = q.front();
    q.pop();
    if (p.y == h - 1 && p.x == w - 1)
        return p.c;
    rep(i, 0, 4)
    {
        int ny = p.y + dy[i], nx = p.x + dx[i];
        if (s[ny][nx] == '.' && (!pass[ny][nx]))
        {
            q.push({ny, nx, p.c + 1});
            pass[ny][nx] = 1;
        }
    }
    return bfs();
}

int main(void)
{
    ll h, n;
    cin >> h >> n;
    vector<pll> a(n);
    ll m = 0;
    rep(i, 0, n)
    {
        cin >> a[i].first >> a[i].second;
        m = max(m, a[i].first);
    }

    vll d(h + m, LINF);
    d[0] = 0;
    rep(i, 0, h + m)
        rep(j, 0, n) if (i - a[j].first >= 0) d[i] = min(d[i], d[i - a[j].first] + a[j].second);
    ll M = INF;
    rep(i, h, h + m) M = min(M, d[i]);
    cout << M << endl;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
int main(){
    char str[25];
    int length = 0;
    int no = 0;
    
    scanf("%s", str);
    length = strlen(str);
    
    for(int i = 0; i < length-1; i++){
        if(no)break;
        
        for(int j = i+1; j < length; j++){
         if(str[i]==str[j]){
            printf("no\n");
            no = 1;
            break;
         }
        }
    }
    if(no==0){
        printf("yes\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define mx *max_element
#define mi *min_element
#define fn for(long long int i =0 ;i <n;i++)
#define fn1 for(long long int i =1;i<=n;i++)
#define fm for(long long int j =0 ;j <m;j++)
#define fm1 for(long long int j =1;j<=m;j++)
#define fi first
#define se second
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
const int N = 1e6;
ll tree[2*N];
vector < pair < ll , ll > > v[N];
int main(){
	Fast;
	ll n  ;
	cin >> n ;
	ll p=-1;
	vector < ll >dp(3);
	fn{
	    vector < ll > new_dp(3,0);
	    vector < ll >ar(3);
	    cin >> ar[0] >> ar[1] >> ar[2];
	    for(int j =0 ;j < 3; j++){
	        for(int k =0 ; k < 3 ; k++){
	            if(k!=j){
	                new_dp[k]= max(new_dp[k],dp[j]+ar[k]);
	            }
	        }
	    }
	    dp=new_dp;
	}
	ll ans =0;
	cout << max({dp[0],dp[1],dp[2]});
	return 0;
}

Measured memory_bytes: 24832
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

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

int n;
vector<int> p;
priority_queue<int, vector<int>, greater<int>> que;

int solve()
{
    que.push(p[0]);
    int cnt = 1;
    for(int i = 1; i < p.size(); i++)
    {
        int num = p[i];
        que.push(p[i]);
        if(que.top() == num) cnt++;
    }
    return cnt;
}

int main()
{
    cin >> n;
    rep(i,n)
    {
        int tmp;
        cin >> tmp;
        p.pb(tmp);
    }
    cout << solve() << endl;
}

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

const ll mod = 1e9 + 7;

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

/*-------------------------------------------*/

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

    int n, m;
    cin >> n >> m;
    cout << (n == m ? "Yes" : "No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator >(const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, int cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

/*--------------------template--------------------*/
int n, m;
vector<pii> v;
int dp[1111][1111], mx[1111][1111];

void dijkstra(Graph &g, vector<Weight> &d, int s)
{
	d.assign(g.size(), INF);
	d[s] = 0;
	typedef pair<Weight, int> P;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, s));
	while (!que.empty())
	{
		Weight dist = que.top().first;
		int v = que.top().second;
		que.pop();
		if (d[v] < dist) continue;
		REP(i, g[v].size())
		{
			Edge e = g[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}


int main()
{
	cin >> n >> m;
	REP(i, m)
	{
		int c, d; cin >> c >> d;
		v.emplace_back(c, d);
	}
	sort(ALL(v));
	REP(i, m) mx[i][i] = v[i].second;
	REP(i, m)FOR(j, i + 1, m) mx[i][j] = max(mx[i][j - 1], v[j].second);
	Graph g(m+1);
	REP(i, m)FOR(j, i, m)
	{
		add_edge(g, i, j + 1, mx[i][j] - v[i].first);
	}
	vector<Weight> dist;
	dijkstra(g, dist, 0);
	cout << n + 1 + dist[m] * 2 << endl;
	return 0;
}

Measured memory_bytes: 7200
using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using Debug = System.Diagnostics.Trace;
using SB = System.Text.StringBuilder;
using static System.Math;
using Number = System.Int32;

namespace Program {
	public class Solver {
		Random rnd = new Random(0);
		public void Solve() {
			var n = rd / 3;
			Console.WriteLine(n * n * n);

		}

		const long INF = 1L << 60;
		static int[] dx = { -1, 0, 1, 0 };
		static int[] dy = { 0, 1, 0, -1 };
		int ri { get { return sc.Integer(); } }
		long rl { get { return sc.Long(); } }
		double rd { get { return sc.Double(); } }
		string rs { get { return sc.Scan(); } }
		public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());

		static T[] Enumerate<T>(int n, Func<int, T> f) {
			var a = new T[n];
			for (int i = 0; i < a.Length; ++i) a[i] = f(i);
			return a;
		}
		static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
	}
}

#region main
static class Ex {
	static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
	static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
		return string.Join(st, ie);
	}
	static public void Main() {
		Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = true });
		var solver = new Program.Solver();
		//* 
		var t = new System.Threading.Thread(solver.Solve, 50000000);
		//t.Start();
		//t.Join();
		//*/
		solver.Solve();
		Console.Out.Flush();
	}
}
#endregion
#region Ex
namespace Program.IO {
	using System.IO;
	using System.Text;
	using System.Globalization;

	public class Printer : StreamWriter {
		public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
		public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
	}

	public class StreamScanner {
		public StreamScanner(Stream stream) { str = stream; }

		public readonly Stream str;
		private readonly byte[] buf = new byte[1024];
		private int len, ptr;
		public bool isEof = false;
		public bool IsEndOfStream { get { return isEof; } }

		private byte read() {
			if (isEof) return 0;
			if (ptr >= len) {
				ptr = 0;
				if ((len = str.Read(buf, 0, 1024)) <= 0) {
					isEof = true;
					return 0;
				}
			}
			return buf[ptr++];
		}

		public char Char() {
			byte b = 0;
			do b = read(); while ((b < 33 || 126 < b) && !isEof);
			return (char)b;
		}
		public string Scan() {
			var sb = new StringBuilder();
			for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
			return sb.ToString();
		}
		public string ScanLine() {
			var sb = new StringBuilder();
			for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
			return sb.ToString();
		}
		public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
		public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
		public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
	}
}

#endregion


Measured memory_bytes: 11092
#include <iostream>
using namespace std;
const long long int MAX_A = 99999;

int main(void){
	long long int	num_digits[100001] = {0};
	int N;
	cin >> N;
	//cout << N;
	for(int i = 0; i < N; ++i){
		int a;
		cin >> a;
		//a--;
		num_digits[a] += 1;
	}
	long long int max_num = -1;
	for(int i = 1; i <= MAX_A-1; ++i){
		long long int sum = num_digits[i-1] + num_digits[i] + num_digits[i+1];
		if(sum > max_num){
			max_num = sum;
		}
	}
	cout << max_num << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define S second
#define F first

using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
const int maxn = 1e6;
int a[maxn];
int32_t main(){
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 0;i < m;i++){
        int a1,b;
        cin >> a1 >> b;
        a[a1]++,a[b]++;
    }
    for (int i = 1;i <= n;i++){
        if (a[i] % 2){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
bool check(int ,int,int,int);
int *line;
int main(){
	int N,A,B;
	cin>>N>>A>>B;
	A-=B;
	line=new int[N];
	for(int i=0;i<N;++i){
		cin>>line[i];
	}
	int dn=1,un=1<<31-1;
	while(dn<un){
		int num=(dn+un)/2;
		if(check(A,B,num,N)){
			un=num;
		}else{
			dn=num+1;
		}
	}
	cout<<dn<<endl;
	return 0;
}
 
bool check(int A,int B,int num,int N){
	long long Bnum=(long long)B*num;
	long long ans=0;
	for(int i=0;i<N;++i){
		long long dnum=(long long)line[i]-Bnum;
		if(dnum>0){
			ans+=(dnum+A-1)/A;
		}
	}
	return ans<=num?true:false;
}

Measured memory_bytes: 640