akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = list(map(int,input().split()))

cnt = 0
reset = True
flag = True
tmp = A[0]
for i in range(1,N):
    if reset:
        if A[i] > tmp:
            flag = True
            reset = False
        elif A[i] < tmp:
            flag = False
            reset = False
    else:
        if flag and A[i] < tmp:
            cnt += 1
            reset = True
        elif not(flag) and A[i] > tmp:
            cnt += 1
            reset = True
    tmp = A[i]
        
    
    
  
print(cnt+1)
        
        
    

Measured memory_bytes: 14224
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	k , n = IN()
	al = list(IN())
	max_dist=k-al[-1]+al[0]
	for pa, pb in zip(al, al[1:]):
		max_dist = max(max_dist, pb-pa)
	print(k-max_dist)
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

using namespace std;
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  long long int a,b,c;
  cin>>a>>b>>c;
  int t=1000;
  int f=0;
  while((a%2==0 && b%2==0 && c%2==0) && t--){
    long long int x=a/2;
    long long int y=b/2;
    long long int z=c/2;
    a=y+z;
    b=x+z;
    c=x+y;
    f++;
  }
  if(f!=1000){
    cout<<f<<endl;
  }else{
    cout<<-1<<endl;
  }




}

Measured memory_bytes: 256
#coding-utf-8
a,b,c=map(int,input().split())
ans=a+b+c
ans=min(ans,abs(b-a)+abs(b-c))
ans=min(ans,abs(c-a)+abs(b-c))
ans=min(ans,abs(a-b)+abs(a-c))
ans=min(ans,abs(c-b)+abs(a-c))
ans=min(ans,abs(c-a)+abs(b-a))
ans=min(ans,abs(c-b)+abs(b-a))
print(ans)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <valarray>

typedef long long i64;

const int N = 400000 + 10, S = 100;

int n, x, y;
char s[N];

std::valarray<i64> sum[N];

void init() {
  static int next[N];
  next[1] = 0;
  for (int i = 2; i <= n; ++i) {
    int j = next[i - 1];
    while (j && s[j + 1] != s[i]) j = next[j];
    j += (s[j + 1] == s[i]);
    next[i] = j;
  }
  sum[0].resize(26);
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1], ++sum[i][s[i] - 'a'];
  x = n - next[n];
  y = x - next[x];
}

std::valarray<i64> solve(i64 m) {
  if (m <= n) return sum[m];
  if (x % y == 0) {
    m -= x;
    return sum[x] + sum[y] * (m / y) + sum[m % y];
  }
  static i64 fib[S];
  static std::valarray<i64> temp[S];
  temp[0] = sum[fib[0] = y];
  temp[1] = sum[fib[1] = x];
  for (int i = 2; i < S; ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    temp[i] = temp[i - 1] + temp[i - 2];
  }
  int k = 2;
  while (fib[k] < m) ++k;
  std::valarray<i64> res(26);
  while (k > 1) {
    if (m >= fib[k - 1]) {
      res += temp[k - 1];
      m -= fib[k - 1];
      k -= 2;
    } else {
      --k;
    }
  }
  res += sum[m];
  return res;
}

int main() {
  i64 l, r;
  scanf(" %s%lld%lld", s + 1, &l, &r);
  n = strlen(s + 1);
  init();
  std::valarray<i64> ans = solve(r) - solve(l - 1);
  for (int i = 0; i < 26; ++i) printf("%lld ", ans[i]);
  return 0;
}


Measured memory_bytes: 52224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll tmp1,tmp2,tmp3;
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
int main(){
  ll n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  tmp1 = -1;
  ll sum = 0;
  rep(i,n){
    if(s[i] == 'L'){
      if(tmp1 == 0){
        sum++;
      }
      tmp1 = 0;
    }else{
      if(tmp1 == 1){
        sum++;
      }
      tmp1 = 1;
    }
  }
  cout << min(n-1,sum+2*k);
}


Measured memory_bytes: 512
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var: ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        x: usize,
        l: [i64; n],
    }
    let mut ans = 1;
    let mut current = 0;
    for i in 0..n {
        current += l[i];
        if current > x as i64 {
            break;
        }
        ans += 1;
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define wi(t) int t;cin>>t;while(t--)
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

int tc=1;

void solve()
    { 
     int x;
     cin>>x;
     if(x>=30)
     yes;
     else
     {
       no;
     }
     
   


    }
     
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
   // wi(t)
    {
    solve();
    }
    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
    u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}







Measured memory_bytes: 10688
program main
	implicit none
	integer i, j, counter
	character(1) cha(1:26)
	character(100000) S
	read(*, *) S
	cha(1)  = 'a'; cha(2)  = 'b'; cha(3)  = 'c'; cha(4)  = 'd'; cha(5)  = 'e'
	cha(6)  = 'f'; cha(7)  = 'g'; cha(8)  = 'h'; cha(9)  = 'i'; cha(10) = 'j'
	cha(11) = 'k'; cha(12) = 'l'; cha(13) = 'm'; cha(14) = 'n'; cha(15) = 'o'
	cha(16) = 'p'; cha(17) = 'q'; cha(18) = 'r'; cha(19) = 's'; cha(20) = 't'
	cha(21) = 'u'; cha(22) = 'v'; cha(23) = 'w'; cha(24) = 'x'; cha(25) = 'y'
	cha(26) = 'z'
	counter = 0
	do i = 1, 26
		do j = 1, len_trim(S)
			if(S(j:j) == cha(i)) then
				counter = counter + 1
				exit
			end if
		end do
		if(counter /= i) then
			write(*, *) cha(i)
			exit
		else if(counter == 26) then
			write(*, *) 'None'
			exit
		end if
	end do
end program main

Measured memory_bytes: 700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define f first
#define s second
const int MAXN=3100;
const int MAXK=19;
const int INF = 1e9;
const ll MOD = 998244353;
ll N,E,K,W,a,b,c,d;
ll dp[MAXN][MAXN];
ll A,B,C,D;

ll ask(ll a, ll b){
  if(a>C||b>D)return 0;
  if(dp[a][b]!=-1)return dp[a][b];
  dp[a][b]=a*ask(a,b+1)%MOD + b*ask(a+1,b)%MOD - a*b*ask(a+1,b+1)%MOD;
  dp[a][b] = (MOD + dp[a][b])%MOD;
  // cerr<<a<<' '<<b<<' '<<dp[a][b]<<'\n';
  // cerr<<a<<' '<<b<<' '<<a*ask(a,b+1) + b*ask(a+1,b) - a*b*ask(a+1,b+1)<<'\n';
  return dp[a][b];
}

int main(){
  cin>>A>>B>>C>>D;
  memset(dp,-1,sizeof(dp));
  dp[C][D]=1;
  cout<<ask(A,B);
}

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

int main(){
	ll n;
	cin>>n;
	vector<ll> h(n),ans(n);
	for(auto& it:h)cin>>it;
	ans[n-1]=0;
	ans[n-2]=abs(h[n-1]-h[n-2]);
	for(ll i=n-2;i>0;i--){
		ans[i-1]=min(abs(h[i]-h[i-1])+ans[i],
			abs(h[i+1]-h[i-1])+ans[i+1]);
	}
	cout<<ans[0]<<'\n';
	return 0;
}	

Measured memory_bytes: 1792
import sys
input=lambda: sys.stdin.readline().rstrip()
a,b,c,d=map(int,input().split())
t=0
while True:
  if t==0:
    c-=b
    if c<=0:
      print("Yes")
      break
    t=1
  else:
    a-=d
    if a<=0:
      print("No")
      break
    t=0



Measured memory_bytes: 9180
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("in.txt");ofstream coutt("out.txt");
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}
int ceil(const int &a,const int &b){return (a-1)/b+1;}
//Read:
//Use __builtin_popcountll for ll

signed main(){
    double a,b;cin>>a>>b;
    a=a*b;
    cout<<(int)a;
}

Measured memory_bytes: 3800
import math
x, y = [int(i) for i in input().split()]

ans = 0
for i in range(1,x+1):
    if i >= y:
        ans += (1/x)*(x+1-i)
        break
    else:
        t = math.ceil(math.log2(y/i))
        ans += (1/x)*pow(0.5,t)

print(ans)

Measured memory_bytes: 3316
#include<iostream>
using namespace std;
int main(){
    int num1[7]={1,3,5,7,8,10,12};
    int num2[4]={4,6,9,11};
    int num3[1]={2};
    int x,y;
    while(cin>>x>>y){
    int f=0;
    for(int i=0;i<7;i++){
        if(x==num1[i]){
            for(int j=0;j<7;j++){
                if(y==num1[j]){
                    cout<<"Yes"<<endl;
                    f=1;
                }
            }
        }
    }
    for(int i=0;i<4;i++){
        if(x==num2[i]){
            for(int j=0;j<4;j++){
                if(y==num2[j]){
                    cout<<"Yes"<<endl;
                    f=1;
                }
            }
        }
    }
    if(f==0){
        cout<<"No"<<endl;
    }
        }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

#define D_MAX 1000000000
#define N_MAX 100000
#define M_MAX 10000

int d;
int n;
int m;

int ad[N_MAX+1];
int ak[M_MAX+1];
int temp[N_MAX+1]; 

void MergeSort(int array[],int left,int right){
  int awork[N_MAX+1];
  int mid;
  int i;
  int j;
  int x;
  int y;
  
  if( left >= right ){
    return;
  }
  
  mid = (left + right) / 2;
  MergeSort( array, left, mid);
  MergeSort( array, mid+1, right);
  
  for( i=left; i<=mid; i++){
    awork[i] = array[i];
  }
  
  j = right;
  for( i=mid+1; i<=right; i++){
    awork[i] = array[j];
    j--;
  }
  
  x = left;
  y = right;
  
  for( i=left; i<=right; i++){
    if(awork[x] <= awork[y]){
      array[i] = awork[x];
      x++;
    }else{
      array[i] = awork[y];
      y--;
    }
  }
}


int calcDist(int k){
  int i;
  int diff;
  int preDiff = 0;
  int minDist = d;
  int tmpDist;
  int halfDist = d >> 1;
  
  for( i=0; i<=n; i++){
    diff = ad[i] - k;
    if( minDist > abs(diff) ){
      minDist = abs(diff);
    }
    preDiff = diff;
  }
  return minDist;
}

/*
int calcDist(int k){
	int i;
	int minDist = d;
	int tmpDist;
	int halfDist = d >> 1;
	
	for( i=1; i<=n; i++){
		tmpDist = abs(ad[i]-k);
		if( tmpDist > halfDist ){
			tmpDist = d-tmpDist;
		}
		if( minDist > tmpDist ){
			minDist = tmpDist;
		}
	}
	return minDist;
}
*/

void input(void){
  int i;
  scanf("%d",&d);
  if( d != 0){
    scanf("%d",&n);
    scanf("%d",&m);
    ad[0] = 0;
    for( i=1; i<=n-1; i++){
      scanf("%d",&ad[i]);
    }
    ad[n] = d;
    for( i=1; i<=m; i++){
      scanf("%d",&ak[i]);
    }
  }
}

int main(void){
  int i;
  int sumDist = 0;
  while( 1 ){
    input();
    if( d == 0 ){
      break;
    }
    MergeSort( ad, 0, n);
    for( i=1; i<=m; i++){
      sumDist += calcDist(ak[i]);
    }
    printf("%d\n",sumDist);
    sumDist = 0;
  }
}




Measured memory_bytes: 8868
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        int n = Integer.parseInt(scan.nextLine());
        double maxProfit = -1000000000;
        double maxR = Integer.parseInt(scan.nextLine());
        double minR = maxR;
        double newR;
        double tmp = -1000000000;

        for (int i=1; i<n; i++){
            newR = Integer.parseInt(scan.nextLine());
            //System.out.printf("%d??????????¨???????, newR:%f, minR:%f, maxR:%f, maxProfit:%f\n", i, newR, minR, maxR, maxProfit);
            if (newR > minR && newR > maxR){
                //System.out.println("aiueo");
                tmp = newR - minR;
                maxR = newR;
            }else if (newR <= minR){
                tmp = newR - minR;
                minR = newR;
                maxR = newR;
            }
            if (tmp > maxProfit)
                maxProfit = tmp;
            //System.out.printf("%d??????????¨???????, newR:%f, minR:%f, maxR:%f, maxProfit:%f\n\n", i, newR, minR, maxR, maxProfit);
        }
        System.out.println((int) maxProfit);
    }
}

Measured memory_bytes: 168428
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    string s;
    cin >> n >> s;
    bool flag=true;
    for (int i=0;i<n/2;i++) {
        if (s[i]!=s[i+n/2]) flag=false;
    }
    if (n%2==1) flag=false;
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100001


int main(){
  int H, i;
  int A[MAX];
  scanf("%d",&H);
  for(i=1;i<=H;i++){
    scanf("%d",&A[i]);
  }
  
  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(i/2 >= 1)printf("parent key = %d, ",A[i/2]);
    if(i*2 <= H)printf("left key = %d, ",A[i*2]);
    if(i*2+1 <= H)printf("right key = %d, ",A[i*2+1]);
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2716
//Don't have to see. start------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin, output: process.stdout
});
var obj; var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error('\n');
  var start = Date.now();
  Main();
  var end = Date.now() - start;
  myerr('time : ' + end + 'ms');
  myerr('memory : ' + Math.round(process.memoryUsage().heapTotal / 1024) + 'KB');
});
function makeClone(obj){return (obj instanceof Set) ? new Set(Array.from(obj)) : JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  return {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(this.hasNext()){return this.list[this.index++];}else{throw 'ArrayIndexOutOfBoundsException ‚There is no more input';}}
  };
}
function myout(s){console.log(s);}
function myerr(s){console.error('debug:' + require('util').inspect(s,false,null));}
//param "no" is
//unknown or outlier : return i. 1: parseInt.
//2: split space. 4: split space and parseInt.
//6: split 1 character. 7: split 1 character and parseInt.
//8: join space. 9: join nextline. 0: join no character.
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(' ');case 4:return i.split(' ').map(Number);case 6:return i.split('');case 7:return i.split('').map(Number);case 8:return i.join(' ');case 9:return i.join('\n');case 0:return i.join('');default:return i;}}catch(e){return i;}}

//Don't have to see. end------------------------------------------
function Main(){
  var N = nextInt();
  var output = 0;
  for(var i = 1; i <= N; i++){
    var count = Math.floor(N / i);
    output += i * (count * (count + 1) / 2);
  }
  myout(output);
}


Measured memory_bytes: 33704
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
bool cmp(LL a, LL b) { return a > b; }
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	std::vector<LL> positive, negative;		  // 记录正数和负数
	LL n, k, cnt_p = 0, cnt_n = 0, cnt_z = 0; // 记录个数

	std::cin >> n >> k;
	int tmp;

	while (n--)
	{
		std::cin >> tmp;
		if (tmp > 0) // 统计正数
		{
			cnt_p++;
			positive.push_back(tmp);
		}
		else if (tmp < 0) // 统计负数
		{
			cnt_n++;
			negative.push_back(tmp);
		}
		else // 统计0
		{
			cnt_z++;
		}
	}

	// 预先排序
	std::sort(positive.begin(), positive.end(), cmp);
	std::sort(negative.begin(), negative.end(), cmp);

	LL n_n = cnt_p * cnt_n;										// 负数的组合个数
	LL n_0 = cnt_z * (cnt_n + cnt_p) + cnt_z * (cnt_z - 1) / 2; // 0的组合个数
	//LL n_p = cnt_n * (cnt_n - 1) / 2 + cnt_p * (cnt_p - 1) / 2; // 正数的组合个数

	if (k <= n_n) //负数
	{
		LL l = positive[0] * negative.back(), r = positive.back() * negative[0]; // 确定二分区间

		while (l <= r)
		{
			LL mid = (l + r) >> 1;
			LL cnt = 0, idx = 0;		   // cnt记录mid前面的个数
			for (LL i = 0; i < cnt_n; i++) // 第一个指针遍历所有的负数，从大到小
			{
				while (true)
				{
					if (idx < cnt_p && positive[idx] * negative[i] <= mid) // 找出mid前的数组合
					{
						idx++;
						continue;
					}
					break;
				} // 保存idx的位置，减少之后循环的次数
				cnt += idx;
			}
			if (cnt < k)
				l = mid + 1;
			else
				r = mid - 1;
		}
		std::cout << l;
	}
	else if (k <= n_n + n_0) // 零
	{
		std::cout << 0;
	}
	else // 正数
	{
		// 颠倒顺序，方便下标处理,从小到大
		std::reverse(positive.begin(), positive.end());

		// 确定取值范围
		LL l = 1e18, r = 0;
		// 防止数据太小
		if (cnt_p >= 2)
		{
			r = std::max(positive.back() * positive[cnt_p - 2], r);
			l = std::min(positive[0] * positive[1], l);
		}
		if (cnt_n >= 2)
		{
			r = std::max(negative.back() * negative[cnt_n - 2], r);
			l = std::min(negative[0] * negative[1], l);
		}

		while (l <= r)
		{
			LL mid = (l + r) >> 1;

			//std::cout << "------------------------------------" << std::endl;
			//std::cout << "l,r,mid: " << l << "," << r << "," << mid << std::endl;

			LL cnt = 0;

			bool calc = true;
			LL idx = 0;
			for (LL i = cnt_p - 1; i >= 0; i--) // 第一个指针遍历所有正数，从大到小
			{
				while (calc)
				{
					if (idx < i && positive[i] * positive[idx] <= mid)
					{
						idx++;
						continue;
					}
					break;
				}

				//std::cout << "idx ps: " << idx << std::endl;

				if (i < idx)
				{
					cnt += i;
					calc = false; // 不用继续进行上面那个while了
				}
				else
				{
					cnt += idx;
				}
			}

			calc = true; // 还原标记
			idx = 0;
			for (LL i = cnt_n - 1; i >= 0; i--) // 遍历所有负数 从小到大(乘积从大到小)
			{
				while (calc)
				{
					if (idx < i && negative[i] * negative[idx] <= mid)
					{
						idx++;
						continue;
					}
					break;
				}

				//std::cout << "idx ng: " << idx << std::endl;

				if (i > idx)
				{
					cnt += idx;
				}
				else
				{
					cnt += i;
					calc = false;
				}
			}

			//std::cout << "cnt,i: " << cnt << "," << k - n_n - n_0 << std::endl;

			if (cnt < k - n_n - n_0)
				l = mid + 1;
			else
				r = mid - 1;
		}
		std::cout << l;
		return 0;
	}

	return 0;
}


Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int d[210][210], s[210][210];


int main(){
    int n;
    int w, h, x, y, S, T;
    while(cin>>n && n){
        rep(i, 210) rep(j, 210) d[i][j] = s[i][j] = 0;
        cin>>w>>h;
        rep(i, n){
            cin>>x>>y;
            d[x][y]=1;
        }
        for(int i = 0; i < 110; i++){
            for(int j = 0; j < 110; j++){
                s[i+1][j+1] = d[i][j]+s[i+1][j];
            }
        }
        for(int i = 0; i < 200; i++){
            for(int j = 0; j < 200; j++){
                s[i+1][j+1] += s[i][j+1];
            }
        }
        int ans = 0;
        cin>>S>>T;
        for(int i = 0; i < 110; i++){
            for(int j = 0; j < 110; j++){
                ans = max(ans, s[i+S][j+T]-s[i][j+T]-s[i+S][j]+s[i][j]);
                //cout<<s[i+S][j+T]-s[i][j+T]-s[i+S][j]+s[i][j]<<endl;
            }
        }
        cout<<ans<<endl;
        // for(int i = 0; i <= w; i++){
        //     for(int j = 0; j <= h; j++){
        //         //cout<<" "<<d[i][j];
        //         printf("%3d", d[i][j]);
                
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
        // for(int i = 0; i <= w+5; i++){
        //     for(int j = 0; j <= h+5; j++){
        //         //cout<<" "<<s[i+1][j+1];
        //         printf("%3d", s[i+1][j+1]);
        //     }
        //     cout<<endl;
        // }

    }
}

Measured memory_bytes: 1504
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using lint=long long;
int MOD=1000000007;

int r,s,p;

signed main(){
    int n,k;cin>>n>>k;
    cin>>r>>s>>p;
    string t;cin>>t;
    vector<vector<int>> dp(n+5,vector<int>(4,0));
    rep1(i,k){
        if(t[i-1]=='r')dp[i][3]=p;
        else if(t[i-1]=='s')dp[i][1]=r;
        else dp[i][2]=s;
    }
    for(int i=k+1;i<=n;++i){
        rep1(j,3){
            dp[i][j]=max(dp[i-k][(j+1)%3+1],dp[i-k][j%3+1]);
        }
        if(t[i-1]=='r')dp[i][3]+=p;
        else if(t[i-1]=='s')dp[i][1]+=r;
        else dp[i][2]+=s;
    }
    int res=0;
    for(int i=n;i>n-k;--i){
        int buf=0;
        rep1(j,3)buf=max(buf,dp[i][j]);
        res+=buf;
    }
    cout<<res<<"\n";
    return 0;
}

Measured memory_bytes: 8800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;

vector<vector<int>> G;
int S, T;

int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
    }
    cin >> S >> T;
    --S, --T;

    vector<vector<int>> dist(N, vector<int>(3, -1));
    dist[S][0] = 0;
    queue<pair<int, int>> q;
    q.push({S, 0});

    while (!q.empty()) {
        int v = q.front().first;
        int p = q.front().second;
        q.pop();
        for (auto nv : G[v]) {
            int np = (p + 1) % 3;
            if (dist[nv][np] == -1) {
                dist[nv][np] = dist[v][p] + 1;
                q.push({nv, np});
            }
        }
    }
    if (dist[T][0] == -1)
        cout << -1 << endl;
    else
        cout << dist[T][0] / 3 << endl;
}

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

int main() {
	int d;
	cin >> d;
	vector<int> c(30);
	vector<int> co(d+5);

	rep(i,26) {
		cin >> c[i];
	}

	vector<int> last(26);

	rep(i, 26) {
		last[i]=0;
	}

	int coun = 0;

	vector<int> t(d + 5);
	
	rep(j, d) {
		vector<int> s(26);
		int count = 0;

		rep(i, 26) {
			cin >> s[i];
		}
		int max=s[0];
		int max_d=0;

		rep(i, 26) {
			if (max <= s[i]) {
				max = s[i];
				max_d = i;
			}
		}

		last[max_d] = j+1;
		count = max;

		rep(i, 26) {
			count -= c[i] * (j+1-last[i]);
		}
		co[j] = max_d;
	}
	
	/*
	rep(j, d) {
	
		rep(i, 26) {

			if ( (t[j]-1) != i) {
				coun -= c[i]*(j + 1 - last[i]);
			}
			else {
				coun += s[i][j];
			//	cout << s[i][j] << endl;
				last[i] = j+1;
			}
		}
		co[j] = coun;
	}
	*/

	rep(j, d) {
		cout << co[j]+1<<endl;
	}

	return 0;
}

Measured memory_bytes: 3584
from heapq import heappop, heappush
inf = float('inf')

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

l = []
res = 0
for i in range(N):
    heappush(l, A[i])
    res += A[i]
ls = []
ls.append(res)

for i in range(N, 2*N):
    heappush(l, A[i])
    res += A[i]
    res -= heappop(l)
    ls.append(res)

A.reverse()

s = []
res = 0
for i in range(N):
    heappush(s, -A[i])
    res += A[i]
ss = []
ss.append(res)

for i in range(N, 2*N):
    heappush(s, -A[i])
    res += A[i]
    res -= -heappop(s)
    ss.append(res)

ss.reverse()

ans = -inf

for i in range(N+1):
    score = ls[i] - ss[i]
    ans = max(ans, score)

print(ans)

Measured memory_bytes: 37212
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  if (N<=9 ){
    cout<< "Yes" << endl;
  }
  else if (N%2==0 && N<=18){
    cout<< "Yes" << endl;
  }
  else if (N%3==0 && N<=27){
    cout<< "Yes" << endl;
  }
  else if (N%4==0 && N<=36){
    cout<< "Yes" << endl;
  }
  else if (N%5==0 && N<=45){
    cout<< "Yes" << endl;
  }
  else if (N%6==0 && N<=54){
    cout<< "Yes" << endl;
  }
  else if (N%7==0 && N<=63){
    cout<< "Yes" << endl;
  }
  else if (N%8==0 && N<=72){
    cout<< "Yes" << endl;
  }
  else if (N%9==0 && N<=81){
    cout<< "Yes" << endl;
  }
  else {
    cout<< "No" << endl;
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll a;
  	ci(a)
  st s;
  	ci(s)
  ll ans=0;
  ll now=0;
  FOR(i,0,a){
	if(s[i]=='D'){
      now--;
      ans=M(ans,now);
    }
    else{
      now++;
      ans=M(ans,now);
    }
  }
  co(ans)
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int n,q;
string s;
vector<char> t(200010),d(200010);

bool c(int x){
  int now=x;
  rep(i,q){
    if(s[now]==t[i]){
      if(d[i]=='L') now--;
      else now++;
    }
    if(now==-1 || now==n) return true;
  }
  return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>q>>s;
    rep(i,q) cin>>t[i]>>d[i];
    int low=-1,high=n,mid;
    rep(i,100){
      mid=(low+high)/2;
      if(c(mid)) low=mid;
      else high=mid;
    }
    int low2=-1,high2=n,mid2;
    rep(i,100){
      mid2=(low2+high2)/2;
      if(c(mid2)) high2=mid2;
      else low2=mid2;
    }
    if(low>=high2) cout<<0<<endl;
    else cout<<n-(low+1)-(n-high2)<<endl;
}

Measured memory_bytes: 1104
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int a[50], b[50], c[50], d[50];

int calc(vector<int> &sol, int q)
{
    int ret = 0;
    for(int i=0;i<q;++i)
    {
        if((sol[b[i]] - sol[a[i]]) == c[i]) ret += d[i];
    }
    return ret;
}

int dfs(int pos, int n, int m, int q, vector<int> &sol)
{
    if(pos == n)
    {
        return calc(sol,q);
    }
    int start = sol.back();
    int ret = -1;
    for(int i = start; i<=m;++i)
    {
        sol.push_back(i);
        ret = max(ret, dfs(pos+1, n, m, q, sol));
        sol.pop_back();
    }

    return ret;
}

int main(){
    std::ios::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> sol;
    for(int i=0;i<q;++i)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    int ret = -1;
    for(int i=1;i<=m;++i)
    {
        sol.push_back(i);
        ret = max(dfs(1, n, m, q, sol), ret);
        sol.pop_back();
    }

    cout << ret << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lop ios; ll t; cin>>t; while(t--)
#define pb push_back
#define vi vector<ll>
#define vivi vector<vector<ll>> 
#define vipa vector<pair<ll,ll>>
#define F first
#define S second
#define M 1000000007
#define kl "\n"
typedef long long ll;
ll lcm(ll x, ll y){ll k=x*y; k/=(__gcd(x,y)); return k;}
ll power(ll x,ll y){ ll r= 1;x = x % M;if(x==0) return 0; while(y>0) {if(y&1) r=(r*x)%M; y=y>>1; x=(x*x)%M;} return r;}  
ll check(string str) 
{ 
    
    ll  n = str.length(); 
    ll  digitSum = 0; 
    for (int i=0; i<n; i++) 
        digitSum += (str[i]-'0'); 
  
    
    return (digitSum % 9 == 0); 
} 
void solve()
{ 
 string s;
 cin>>s;
 if(check(s)) cout<<"Yes";
 else cout<<"No";
}
int main() 
{ 
    // lop
    solve();
	return 0; 
} 




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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long;
#define REP(i,s,N) for (int i=s; i<N; i++)

int main() {
	vi a(3,0);
	int ans = 1;
	REP(i,0,3) cin >> a[i];
	sort(a.begin(), a.end());
	if(a[0]!=a[1]) ans++;
	if(a[1]!=a[2]) ans++;
	cout << ans << endl;
}

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

using namespace std;

const int N = 13;

int c[N];
int a[N][N];
int tem[N];

int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	for(int i=0; i<n; i++)
	{
		cin>>c[i];
		for(int j=0; j<m; j++) cin>>a[i][j];
	}
	int ans = 0x3f3f3f3f;
	for(int i=1; i<(1<<n); i++)
	{
		int cnt = 0;
		memset(tem, 0, sizeof tem);
		for(int j=0; j<n; j++)
		{
			if((i >> j) & 1)
			{
				cnt += c[j];
				for(int k=0; k<m; k++)
				{
					tem[k] += a[j][k];
				}
			}
		}
		int flag = 0;
		for(int k=0; k<m; k++)
		{
			if(tem[k] < x)
			{
				flag = 1;
				break;
			}
		}
		if(flag == 0)
		{
			ans = min(ans, cnt);
		}
	}
	if(ans == 0x3f3f3f3f) puts("-1");
	else cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ff first
#define ss second
#define INF (ll) (1e9)
#define mod (ll) (1e9 + 7)
#define endl "\n"
#define tt ll testcase; cin>>testcase; while(testcase--)
 
const int mxn = 1*(1e5) + 5;
ll n, m;


// 2 methods:
// m-1:  O(N*M*M)

// m-2: use prefix sums to add value over interval
		// O(N*M)
 
void solve(){	
	cin >> n >> m;
	ll a[n];
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}	
	ll dp[m+1] = {};
	dp[0] = 1;
	for(int i=0; i<n; i++) {
		ll upto = a[i];
		ll sum[m+2] = {};
		for(int j = m; j>=0; j--) {
			// for(int l = j+1; l<=min(upto+j, m); l++) {
			// // for(int l = min(j+upto, m); l > j; l--) {
			// 	dp[l] += dp[j];
			// 	if(dp[l] > mod) {
			// 		dp[l] -= mod;
			// 	}
			// }
			sum[min(upto+j, m)+1] -= dp[j];
			sum[j+1] += dp[j]; 
		}
		ll s=0;
		for(int i=0; i<=m; i++) {
			s += sum[i];
			// s %= mod;
			dp[i] += s;
			dp[i] %= mod;
		}
	}
	// for(int i=0; i<=m; i++) {
	// 	cout << dp[i] << " ";
	// }
	cout << dp[m];
}
 
int main(){
    fast;
    #ifndef ONLINE_JUDGE 
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout); 
    #endif 
     // tt
        solve();
    return 0;
}

Measured memory_bytes: 5160
// abc168_d
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


struct Graph {

    int n;
    vector<vector<int>> edges;
    vector<int> par;
    vector<int> dist;

    Graph(int n_): n(n_), edges(n_), par(n_, -1), dist(n_, INF) {}

    void add_edge(int u, int v){
        edges[u].emplace_back(v);
        edges[v].emplace_back(u);
    }

    void bfs(void) {

        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push(P(0, 0));

        dist[0] = 0;

        while (!pq.empty()){
            P p = pq.top(); pq.pop();

            int cost = p.first;
            int u = p.second;

            for (auto v: edges[u]){

                int ncost = cost + 1;

                if (ncost < dist[v]){
                    dist[v] = ncost;
                    par[v] = u;
                    pq.push(P(ncost, v));
                }
            }
        }
    }
};



int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, M;
    cin >> N >> M;
    Graph g(N);
    REP(i, M){
        int a, b;
        cin >> a >> b; a--; b--;
        g.add_edge(a, b);
    }

    g.bfs();

    REP(i, N){
        if (g.dist[i] == INF){
            print("No");
            return 0;
        }
    }
    
    print("Yes");
    REPN(i, 1, N){
        print(g.par[i]+1);
    }


    return 0;
}


Measured memory_bytes: 11208
#include <iostream>
#include <complex>
#include <utility>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef complex<double> Point, Vector;
typedef pair<Point, Point> Segment, Line;
typedef vector<Point> Polygon;

#define X real()
#define Y imag()
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

// 平面走査による線分交差
#define BOTTOM 0
#define LEFT 1
#define RIGHT 2
#define TOP 3

struct EndPoint{
    Point p;
    int seg, st; // 入力線分のID, 端点の種類
    EndPoint() {}
    EndPoint(Point p, int seg, int st): p(p), seg(seg), st(st) {}

    bool operator < (const EndPoint &ep) const{
        // y 座標が小さい順に整列
        if(p.Y == ep.p.Y){
            // y が同一の場合は、下端点、左端点、右端点、上端点の順に並べる
            return st < ep.st;
        }
        else{
            return p.Y < ep.p.Y;
        }
    }
};

// 端点のリスト
EndPoint EP[2 * 100000];

// 線分交差問題: マンハッタン幾何
int manhattanIntersection(vector<Segment> S){
    int n = S.size();

    for(int i=0, k=0; i<n; i++){
        // 端点 p1, p2 が左下を基準に並ぶように調整
        if(S[i].first.Y == S[i].second.Y){
            if(S[i].first.X > S[i].second.X){
                swap(S[i].first, S[i].second);
            }
        }
        else if(S[i].first.Y > S[i].second.Y){
            swap(S[i].first, S[i].second);
        }

        if(S[i].first.Y == S[i].second.Y){
            // 水平線分を端点リストに追加
            EP[k++] = EndPoint(S[i].first, i, LEFT);
            EP[k++] = EndPoint(S[i].second, i, RIGHT);
        }
        else{
            EP[k++] = EndPoint(S[i].first, i, BOTTOM);
            EP[k++] = EndPoint(S[i].second, i, TOP);
        }
    }

    // 端点の y 座標に関して昇順に整列
    sort(EP, EP + (2 * n));

    set<int> BT;
    BT.insert(1000000001);
    int cnt = 0;

    for(int i=0; i<2*n; i++){
        if(EP[i].st == TOP){
            // 上端点を削除
            BT.erase(EP[i].p.X);
        }
        else if(EP[i].st == BOTTOM){
            // 下端点を追加
            BT.insert(EP[i].p.X);
        }
        else if(EP[i].st == LEFT){
            set<int>::iterator b = BT.lower_bound(S[EP[i].seg].first.X);
            set<int>::iterator e = BT.upper_bound(S[EP[i].seg].second.X);
            cnt += distance(b, e);
        }
    }

    return cnt;
}

int main(){
    int n; cin>>n;
    vector<Segment> seg;
    while(n--){
        double x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2;
        seg.emplace_back(Point(x1, y1), Point(x2, y2));
    }

    cout << manhattanIntersection(seg) << endl;
}


Measured memory_bytes: 16356
n = int(input())
s = input()

ans = 0
for i in range(n-1):#iは左側の最大のindex
    tmp = []
    cnt = 0
    for j in range(i+1):
        if s[j] not in tmp:
            tmp.append(s[j])
    for j in range(i+1,n):
        if s[j] in tmp:
            cnt += 1
            tmp.remove(s[j])
    if ans < cnt:
        ans = cnt
print(ans)

Measured memory_bytes: 3064
H,W,K=gets.chomp.split(" ").map(&:to_i)
rets=[]
count=1
H.times do
    ret=[]
    s=gets.chomp
    ss=s.split("#", -1)
    if ss.length > 1
        ret.push(Array.new(ss[0].length,count))
        (1..(ss.length-1)).each do |i|
            ret.push(Array.new(ss[i].length+1,count))
            count+=1
        end
    else
        ret = rets[-1] if !rets.empty?
    end
    rets.push(ret.flatten)
end
c=0
while rets[c].empty? do
    c+=1
end
c.times do
    puts rets[c].join(" ")
end
(c..(H-1)).each do |i|
    puts rets[i].join(" ")
end


Measured memory_bytes: 16252
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

ll pow(ll a, ll b) {
    ll ret = 1;
    while(b > 0) {
        if (b&1) ret = (a * ret) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

ll factorial(ll a, ll b) {
    ll ret = 1;
    for (ll i = 0; i < b; ++i) {
        ret = (ret * a) % mod;
        --a;
    }
    return ret;
}

ll inv(ll a) {
    return pow(a, mod-2);
}

ll combination(ll a, ll b) {
    return factorial(a, b) * inv(factorial(b, b)) % mod;
}

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll total = pow(2LL, n) - 1;
    ll a_num = combination(n, a);
    ll b_num = combination(n, b);
    ll ans = total;
    ans = (ans - a_num < 0) ? ans - a_num + mod : ans - a_num;
    ans = (ans - b_num < 0) ? ans - b_num + mod : ans - b_num;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


S = ST()
Q = I()

switch = True
prefix = ""
suffix = ""
for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        if switch:
            switch = False
        else:
            switch = True
    else:
        if switch:
            if query[1] == "1":
                prefix = query[2] + prefix
            else:
                suffix = suffix + query[2]
        else:
            if query[1] == "1":
                suffix = suffix + query[2]
            else:
                prefix = query[2] + prefix

ans = prefix + S + suffix
if switch:
    print(ans)
else:
    print(ans[::-1])


Measured memory_bytes: 224972
#include <bits/stdc++.h>
using namespace std;
int main(){
    int X,A,B;
    cin >> X >> A >> B;
    if (( A - B ) >= 0) cout << "delicious" << endl;
    else if((B - A) <= X ) cout << "safe" << endl;
    else cout << "dangerous" << endl;
}

Measured memory_bytes: 256
import itertools
n,m,q = map(int, input().split())
candidates = [i for i in range(1,m+1)]
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  a[i], b[i], c[i], d[i]  = map(int, input().split())

max_score = 0
for A in itertools.combinations_with_replacement(candidates, n):
  A = list(A)
  score = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      score += d[i]
  max_score = max(max_score, score)
print(max_score)

Measured memory_bytes: 68524
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Security.Cryptography.X509Certificates;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var f = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var N = f[0];
            var M = f[1];
            var X = f[2];
            var seconds = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int left = 0;
            int right = 0;
            for (int i = 0; i < N; i++)
            {
                if (!seconds.Contains(i))
                {
                    continue;
                }
                if (i <= X)
                {
                    left++;
                }
                else
                {
                    right++;
                }
            }

            Console.WriteLine(left < right ? left : right);
        }
    }
}

Measured memory_bytes: 13396
//
// Created by Ильдар Ялалов on 28.10.2019.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 2e5 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100) * 1.5;
typedef long long li;
const li MOD = 1000000000949747713ll;

template<class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
    out << "( " << rhs.first << " , " << rhs.second << " )";
    return out;
}


void solve() {
    int n;
    cin >> n;
    if(n % 2 == 0){
        cout << n/2 -1 ;
    } else{
        cout << n/2;
    }
    cout <<"\n";

}


signed main() {
#ifdef zxc
//    debug = 1;
    freopen("../input.txt", "r", stdin);
    //  freopen("../output.txt", "w", stdout);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();
    if (debug)
        cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

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

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define rep(i,n) for(int i=0; i<(int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

//constexpr ll mod = 998244353;
constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

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

  int n, k; cin >> n >> k;
  cout << n-k+1 << endl;
}

Measured memory_bytes: 256
n = int(input())
a = input()
b = input()
c = input()

ans = 0
for i in range(n):
    if a[i] == b[i] == c[i]:
        pass
    elif a[i] == b[i] or b[i] == c[i] or a[i] == c[i]:
        ans += 1
    else:
        ans += 2

print(ans)

Measured memory_bytes: 38256