akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static void Main()
    {
        bool flag = false;
        int[,] A = new int[3, 3];
        bool[,] check = new bool[3, 3];
        for (int i = 0; i < 3; i++)
        {
            string[] input = Console.ReadLine().Split();
            for(int j = 0; j < 3; j++) { A[i, j] = int.Parse(input[j]);check[i, j] = false; }
        }
        int N = int.Parse(Console.ReadLine());
        for(int i = 0; i < N; i++)
        {
            int b = int.Parse(Console.ReadLine());
            for(int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 3; k++)
                {
                    if (b == A[j, k]) check[j, k] = true;
                }
            }
        }
        for(int i = 0; i < 3; i++)
        {
            if (check[i, 0] == true && check[i, 1] == true && check[i, 2] == true) flag = true;
            if (check[0, i] == true && check[1, i] == true && check[2, i] == true) flag = true;
        }
        if(check[0, 0] == true && check[1, 1] == true && check[2, 2] == true) flag = true;
        if (check[0, 2] == true && check[1, 1] == true && check[2, 0] == true) flag = true;
        if (flag == true) { Console.WriteLine("Yes"); }
        else { Console.WriteLine("No"); }
    }
}

Measured memory_bytes: 11092
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
   return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
   os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n;cin>>n;
  cout<<((n+999)/1000)*1000-n<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 3652
n = int(input())
a = list(map(int, input().split()))
 
for i in range(1, n):
    print(' '.join(list(map(str, a))))
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = v
 
print(' '.join(list(map(str, a))))

Measured memory_bytes: 7696
#include <cstdio>
#include <iostream>

int main(int argc, char const* argv[]) {
	char s[3];
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		scanf("%c", &s[i]);
		if (s[i] == '1') {
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}


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

int main(){
  int N,M;
  cin>>N>>M;
  vector<pair<int64_t,int64_t>> A(N);
  for(int i=0;i<N;++i){
    cin>>A.at(i).first>>A.at(i).second;
  }

  sort(A.begin(),A.end());
  int64_t cost=0;
  for(int i=0;i<N;++i){
    if(M<=A.at(i).second){
      cost=cost+A.at(i).first*M;
      break;
    }
    else{
      cost=cost+A.at(i).first*A.at(i).second;
      M=M-A.at(i).second;
    }
  }

  cout<<cost<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main() {
  int64_t n,k;
  cin >> k >> n;
  vector<int64_t> data(n);
  for ( int i = 0 ; i < n ; i++ ) {
    cin >> data.at(i);
  }
  
  sort(data.begin(),data.end());
  int64_t m = k-data.at(n-1)+data.at(0);
  
  vector<int64_t> vec(n-1);
  for ( int i = 0 ; i < n-1 ; i++ ) {
    
      vec.at(i) = data.at(i+1) - data.at(i);
  }
  
  sort(vec.begin(),vec.end());
  int64_t ans = max(m,vec.at(n-2) );
  cout << k-ans << endl;
}

Measured memory_bytes: 3328
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    void solve() throws IOException {
        int n = ni();
        long[] a = nla(n);

        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }

        if (sum % ((long) n * (n + 1) / 2) != 0) {
            out.println("NO");
            return;
        }

        long m = sum / ((long) n * (n + 1) / 2);

        long cnt = 0;

        for (int i = 1; i < n; i++) {
            if ((a[i] - a[i - 1] - m) % n != 0) {
                out.println("NO");
                return;
            }
            if (a[i] - a[i - 1] - m < 0) {
                cnt += Math.abs(a[i] - a[i - 1] - m) / n;
            }
        }
        if ((a[0] - a[n - 1] - m) % n != 0) {
            out.println("NO");
            return;
        }
        if (a[0] - a[n - 1] - m < 0) {
            cnt += Math.abs(a[0] - a[n - 1] - m) / n;
        }

        if (cnt > m) {
            out.println("NO");
            return;
        }

        out.println("YES");
    }

    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }

    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }

    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 24724
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_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);
}


#define ARRAY_MAX 100005
const int INF = 1e9 + 7;


int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

const int MOD = 1e9 + 7;



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}
/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);
	return (x / tmp) * y;
}


/******************************************************************************************/


int main() {

	
	ll n;
	cin >> n;
	vector<pll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].second >> a[i].first;
	}

	ll now = 0;

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

	for (int i = 0; i < n; i++)
	{
		if (now + a[i].second <= a[i].first) {
			now += a[i].second;
		}
		else
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;


	return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>	

using namespace std;

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

	cout << min(A * N, B) << endl;

	return 0;
}

Measured memory_bytes: 256
<?php
$n = trim(fgets(STDIN));
$a = explode(" ", trim(fgets(STDIN)));
$average = array_sum($a) / $n;
$min = 10**10;
foreach($a as $i => $b){
  $diff = abs($b - $average);
  if($diff < $min){
    $min = $diff;
    $I = $i;
  }
}
echo $I;

Measured memory_bytes: 4604
#include <stdio.h>

int main() {
    int x, y, z, a=0, b=0, c=0;
    scanf("%d%d%d", &x, &y, &z);
    a = z;
    b = x;
    c = y;
    printf("%d %d %d", a, b, c);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#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 keta(int n) {
    int res;
    for(int i = 0; i < 100; i++) {
        n = n / 10;

        if(n == 0) {
            res = i + 1;
            break;
        }
    }
    return res;
}

ll risi(ll n) {
    ll y = n / 100;
    ll res;
    res = n + y;
    return res;
}
int main() {
    ll x;
    cin >> x;
    ll t = 100;
    rep(i, 100000000) {
        if(risi(t) >= x) {
            cout << i + 1 << endl;
            break;
        }
        t = risi(t);
    }
}


Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
	int a,b,d,r;
	double A,B,f;
	scanf("%d %d",&a,&b);
	A=a;
	B=b;
	d=a/b;
	r=a%b;
	f=A/B;
	printf("%d %d %0.5f\n",d,r,f);
	return 0;
}

Measured memory_bytes: 636
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)*}
    };
}

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)*}
    };
}

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, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
fn main(){
    input!{
        n:usize,
        an:[(usize,usize,usize);n-1],
    }
    for j in 0..n {
        let mut ans = 0;
        for k in j..n-1 {
            if ans < an[k].1 {
                ans = an[k].1;
            } else if ans % an[k].2 == 0 {
            } else {
                ans += an[k].2 -  ans % an[k].2;
            }
            ans += an[k].0;
        }
        println!("{}",ans);
    }
}

Measured memory_bytes: 4352
#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 r = 0, b = 0, n;
    string s;
    cin >> n >> s;
    rep(i, n)(s[i] == 'R' ? r : b)++;
    cout << (r > b ? "Yes" : "No");
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var tmp = lines[0].split(' ');
 var n = Number(tmp[0]);
 var m = Number(tmp[1]);
 var day = lines[1].split(' ');
 for(i=0; i<m; i++){
   n -= Number(day[i]);
 }

 if(n < 0){
   n = -1;
 }

 console.log(n);
});

Measured memory_bytes: 30976
#include<stdio.h>
int main(void){
	int n,i;
	int a[1000];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=n-1;i>=1;i--){
		printf("%d ",a[i]);
	}
	printf("%d\n",a[0]);
	return 0;
}	


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

using namespace std;

int main() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector < char > v;
	v.push_back(s[0]);
	for (int i = 1; i < s.size(); i++)
		if (s[i] != v[v.size() - 1]) v.push_back(s[i]);
	cout<<v.size();
}

Measured memory_bytes: 768
n=int(input())
a=[int(input()) for i in range(n)]

if a[0]!=0:
  print(-1)
  exit()

cnt=0
for i in range(1,n):
  if a[i]==0:
    continue
  elif a[i]==a[i-1]+1:
    cnt+=1
  elif a[i]<=a[i-1]:
    cnt+=a[i]
  else:
    print(-1)
    exit()

print(cnt)

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

static int comp_int(const void *p1, const void *p2)
{
    return *(int*)p1 - *(int*)p2;
}

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

    qsort(v, n, sizeof(int), comp_int);
    double ret = v[0];
    for (i = 1; i < n; i++) {
        ret = (ret + v[i]) / 2;
    }

    printf("%.10lf\n", ret);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    char a[55][55],c;
    int i,j,h,w,sum=0,b[55][55];
    while(cin >> h >> w){
           // getchar();
       for(i = 0 ; i < h; i++)
        {for(j = 0 ; j < w; j++)
          {cin >> c;
           if(c=='#')
           a[i][j]=c;
           else
           a[i][j]=0;

          }
          //getchar();
        }
    for(i = 0 ; i < h; i++)
        for(j = 0 ; j < w; j++)
        {
            if(a[i][j] != '#')
            {
            if(a[i-1][j-1]=='#'&&(i-1>=0))
                sum++;
            if(a[i-1][j]=='#'&&(i-1>=0))
                sum++;
            if(a[i-1][j+1]=='#'&&(i-1>=0))
                sum++;
            if(a[i][j-1]=='#'&&(j-1>=0))
                sum++;
            if(a[i][j+1]=='#'&&(j+1<w))
                sum++;
            if(a[i+1][j-1]=='#'&&(i+1<h&&j-1>=0))
                sum++;
            if(a[i+1][j]=='#'&&(i+1<h))
                sum++;
            if(a[i+1][j+1]=='#'&&(i+1<h&&j+1<w))
                sum++;
            b[i][j]=sum;sum=0;
            }
        }
        for(i = 0 ; i < h; i++)
        {for(j = 0 ; j < w; j++)
            if(a[i][j]!='#')
            cout << b[i][j] ;
            else
             cout << '#';
        cout << endl;
        }

    }
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>

using namespace std; 

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


int main() {
    
  int i, count = 0;
  string S;

  cin >> S;

  REP(i, S.length()){
    if(S[i] == 'x'){
		count++;
	}
  }

  if(count >= 8){
	cout << "NO" << endl;
  } else {
	cout << "YES" << endl;
  }

  return 0;
}

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
void keisan(long long *a,long long b,char c)
{
   if (c == '+')
      *a += b;
   else if(c == '-')
      *a -= b;
   else if(c == '*')
      *a *= b;
}



int main()
{
   long i,j,k;
   long f;
   long n;
   long q;
   long cnt = 0;
   long h;
   long left,right,mid;
   long ans = 0;
   long long b[100];
   char a[1000];
   char tmp[9];
   int end = 0;
   char c;

   fgets(a,1005,stdin);

   j = 0;
   f = 0;
   k = -1;
   while (end == 0) {
      if(a[k+1] != '+' && a[k+1] != '-' && a[k+1] != '*' && a[k+1] != 0) {
         for(i = k+2;;i++) {
            if(a[i] == ' ') {
               j = i;
               break;
            }
         }

         for (i = 0; i < j-k-1; i++) {
            tmp[i] = a[k+1+i];
         }
         tmp[i] = 0;
         k = j;

         b[f] = atol(tmp);
         f++;
      }
      else if(a[k+1] == '+' || a[k+1] == '-' || a[k+1] == '*') {
         keisan(&b[f-2],b[f-1],a[k+1]);
         f--;
         k += 2;
      }
      else if(a[k+1] == 0)
         end = 1;
   }
   printf("%lld\n",b[0]);

   return 0;
}

Measured memory_bytes: 964
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int k = sc.nextInt();
    ArrayList<Integer>ans  = new ArrayList<>();
    
    int cou = 0;
    for(int i=a; i<=a+(k-1); i++) {
    	if(i <= b) {
    	if(!ans.contains(i)){		
    	      ans.add(i);
    	      cou++;
    	}
    }
    }
    for(int i=b; i>=b-(k-1); i--) {
    	if(i>=a) {
    	if(!ans.contains(i)){		
  	      ans.add(i);
  	      cou++;
    	}
  }
    }
    Collections.sort(ans);
    for(int i=0; i<cou; i++) {
    System.out.println(ans.get(i));
    		}
}
}

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
typedef pair<li, li> PI;


int main(void)
{
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	cout << (s < t ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
  
int main(){
 int i,j,tmp,num=0,card[4][13];
 char mark='Z';
   
 for(i=0;i<4;i++){
  for(j=0;j<13;j++){
   card[i][j]=0;
  }
 }
   
 scanf("%d",&tmp);
 for(i=0;i<tmp;i++){
  scanf("%*c%c %d",&mark,&num);
  switch(mark){
   case 'S':
             card[0][num-1]=1;
             break;
   case 'H':
             card[1][num-1]=1;
             break;
   case 'C':
             card[2][num-1]=1;
             break;      
   case 'D':
             card[3][num-1]=1;
             break;          
  }
 }
   
 for(i=0;i<4;i++){
  for(j=0;j<13;j++){
   if(card[i][j]==0){
    switch(i){
     case 0:
             printf("S %d\n",(j+1));
             break;
     case 1:
             printf("H %d\n",(j+1));
             break;
     case 2:
             printf("C %d\n",(j+1));
             break;
     case 3:
             printf("D %d\n",(j+1));
             break;
    }
   }
  }
 }
 return 0;
}

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

#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int NAX = 2e5 + 5, MOD = 1000000007;

struct Solution
{
    Solution() {}
    void solveCase();
};

void Solution::solveCase()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    ll res = 0;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a[i];
        res = (res + sum * a[i]) % MOD;
        sum += a[i];
        sum %= MOD;
    }
    cout << res << '\n';
}

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
    // cin >> t;
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef LOCAL
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}


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

int main()
{
        string n,m;
        cin>>n>>m;
        bool ans = true;
        for(int i = 0;i<n.length();i++)
        {
                if(n[i]!= m[i])
                {       
                        ans = false;
                }
        }
        if(ans == false)
        {
                cout << "No" << endl;
        }
        else
        {
                cout << "Yes" << endl;
        }
}



Measured memory_bytes: 3624
N,M = map(int,input().split())
ans = ['-1']*(N+1)
flg = True
for i in range(M):
  d,n = map(int,input().split())
  if (ans[d]=='-1') or (ans[d]==str(n)):
    ans[d] = str(n)
  else:
    flg = False
    break
if flg:
  ans = ans[1:]
  if (N!=1) and (ans[0]=='0'):
    print(-1)
  else:
    ans = ''.join(ans)
    ans = ans.replace('-1','0')
    if N==1:
      print(int(ans))
    elif ans[0]=='0':
      ans = ans[1:]
      print(''.join(['1',ans]))
    else:
      print(int(ans))
else:
  print(-1)


Measured memory_bytes: 3064
a,b,m=map(int,input().split())
a=[]
b=[]
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ans=[]

for i in range(m):
    x,y,c=map(int,input().split())
    x-=1
    y-=1
    ans.append(a[x]+b[y]-c)
ans.append(min(a)+min(b))
print(min(ans))

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

#define REP(i, n) for(int (i) = 0; (i) < (int)(n); (i)++)
#define REPR(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 1e9

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

typedef long long ll;

using namespace std;

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '+')
        {
            ans++;
        }
        else
        {
            ans--;
        } 
    }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
constexpr auto INF = 2147483647;
typedef long long ll;

int main(){

  int N, W, ans;
  ans = 0;
  cin >> N >> W;
  vector<int> value(N+1), weight(N+1);
  rep(i,N){
    cin >> value[i+1]  >> weight[i+1];
  }

  vector<vector<int>> costDP(N+1, vector<int>(W+1));
  for(int i=0; i<N+1;i++){
    for(int j=W; j>=0;j--){
      if(i==0) costDP[i][j] = 0;
      else if(j + weight[i] > W) costDP[i][j] = costDP[i-1][j];
      else costDP[i][j] = max(costDP[i-1][j],costDP[i][j+weight[i]] + value[i]);
      if(i == N) ans = max(ans, costDP[i][j]);
    }
  }

  // cout << endl;
  // rep(i,N+1){
  //   rep(j,W+1) cout << costDP[i][j] << " ";
  //   cout << endl; 
  // }

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


Measured memory_bytes: 6756
h=int(input())
w=int(input())
n=int(input())

if h>w:
    if n%h==0:
        ans=n//h
    else:
        ans=n//h+1
else:
    if n%w==0:
        ans=n//w
    else:
        ans=n//w+1

print(ans)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
vector<int> vec[100001];
int deg[100001],ord[100001],n,m,a,b,sz;
queue<int> q;
int main()
{
	cin>>n>>m;
	for (int i=0;i<n-1+m;i++)
	{
		cin>>a>>b;
		a--; b--;
		deg[a]++;
		vec[b].pb(a);
	}
	for (int i=0;i<n;i++) if (deg[i]==0) q.push(i);
	while (!q.empty())
	{
		int v=q.front();
		q.pop();
		ord[v]=sz++;
		for (int j=0;j<vec[v].size();j++)
		{
			int to=vec[v][j];
			deg[to]--;
			if (deg[to]==0) q.push(to);
		}
	}
	for (int i=0;i<n;i++)
	{
		int mn=100001,pos=-1;
		for (int j=0;j<vec[i].size();j++)
		{
			int to=vec[i][j];
			if (mn>ord[to]) mn=ord[to],pos=to;
		}
		cout<<pos+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 7552
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <limits>
#include <cstring>

#define FOR(i,b,n) for(int i=b;i<n; i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))

using namespace std;

int a[10], b[10];
int asum = 0, bsum = 0;
void solve()
{
	FOR(i, 0 ,20)
	{
		int t;
		cin >> t;
		
		if( i >= 10 )
			b[i-10] = t;
		else
			a[i] = t;
	}
	
	sort(a, a+10, greater<int>());
	sort(b, b+10, greater<int>());
	
	FOR(i, 0, 3)
	{
		asum += a[i];
		bsum += b[i];
	}
	
	cout << asum << " " << bsum << endl;
	return;
}

int main()
{
	solve();
	return 0;
}

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

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll lcm = c*d/__gcd(c,d);
	ll cnt = b/c - (a-1)/c + b/d - (a-1)/d - b/lcm + (a-1)/lcm;
	cout << (b - a + 1) - cnt;
}

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

int R, C;
int d[50][50];
char t[50][50];
int bk = 0;
int main(){
  cin >> R >> C;
  rep(i, R){
    rep(j, C){
      cin >> t[i][j];
    }
  }
  rep(i, R){
    rep(j, C){
      if(t[i][j] == '#') bk++;
      d[i][j] = -1;
    }
  }
  queue<P> que;
  que.push(P(0, 0));
  d[0][0] = 1;
  int nx, ny, tx, ty;
  int dx[4] = {1, -1, 0, 0};
  int dy[4]= {0, 0, 1, -1};
  while(que.size()){
    P p = que.front();
    que.pop();
    t[ny][nx] = '#';
    ny = p.first;
    nx = p.second;
    rep(i, 4){
      ty = dy[i] + ny;
      tx = dx[i] + nx;
      if( tx >= 0 && tx < C && ty >= 0 && ty < R && t[ty][tx] == '.' && d[ty][tx] == -1){
        que.push(P(ty, tx));
        d[ty][tx] = d[ny][nx] + 1;
      }
    }
  }
  if(d[R-1][C-1]>= 0){
    cout << R * C - d[R-1][C-1] - bk  << endl;
  }else{
    cout << "-1" << endl;
  }
  return 0;
}


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

int main()
{
	int n;
	cin >> n;
	int ans = 0;
	int vvv;
	cin >> vvv;
	ans = vvv;
	for(int i = 2; i < n; i++){
		int t;
		cin >> t;
		ans += min(vvv,t);
		vvv = t;
	} 
	ans += vvv;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define reptr(i,n) for(int (i)=(n);(i)>=0;--(i))
#define All(x) (x).begin(),(x).end()
const ll MOD=1e9+7;
using namespace std;

ll a[1005];
int main(){
  ll N,ans=1;
  cin >> N;
  memset(a,0,sizeof(a));
  for(int i=2;i<=N;i++){
    int tmp=i;
    for(int j=2;j<=i&&tmp!=1;j++){
      while(tmp%j==0){
        a[j]++;
        tmp/=j;
      }
    }
  }
  for(int i=2;i<=N;i++){
    ans*=(a[i]+1);
    ans%=MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int main(){
  int x, y, z; cin >> x >> y >> z;
  printf("%d %d %d\n", z, x, y);

}

// EOF


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59


int main(){
  ll i,j;
  ll a,b,c;
  cin>>a>>b>>c;
  if(a==b&&b==c) {
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<numeric>
#include<math.h>
#include<vector>
using namespace std;

int euclid( int a, int b )
{
    int temp;

    if( a < b ) { temp = a; a = b; b = temp; }
    if( b < 1 ) return -1;

    if( a % b == 0 ) return b;
    return euclid( b, a % b );
}

int main(){
    int N, X, x[1000000];
    cin >> N >> X;
    for(int i=1; i<=N; ++i){
        cin >> x[i];
    }
    x[N+1] = X;
    sort(x+1, x+N+2);
    int d[1000000];
    for(int i=1; i<=N; ++i) d[i] = x[i+1] - x[i];
    int ans;
    if(N == 1) ans = d[1];
    else ans = euclid(d[1], d[2]);
    for(int i=3; i<=N-1; ++i) ans = euclid(ans, d[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx,avx2,tune=native")
//#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds; 
using namespace __gnu_cxx;
using namespace std;
using ll = long long;

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define precision(n) fixed<<setprecision(n)

#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("output.txt","w",stderr);
    #endif
}
template<typename T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update >;
template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T> >;
template<typename T> void done(T ans) {cout << ans << "\n"; exit(0);}

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);

clock_t time_p=clock();
void printTime(){
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}


const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int main() {
    io();
    int n;
    cin >> n;
    int flag = 0;
    while(n) {
        if(n % 10 == 7)
            flag = 1;
        n = n / 10;
    }
    cout << (flag == 1 ? "Yes\n" : "No\n");
    
}




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

int main() {
int N;
  cin >> N;
int A[N];
  int B[N];
  int C[N];
  int k = -2;
  int result = 0;
  for(int a = 0;a < N;a++)cin >> A[a];
  for(int a = 0;a < N;a++)cin >> B[a];
  for(int a = 0;a < N-1;a++)cin >> C[a];
  for(int a = 0;a < N;a++){
    result += B[a];
    
  }
  for(int a = 0;a < N-1;a++){
   if(A[a] + 1 == A[a+1]){
     result += C[A[a] - 1];
   }
    
  }
  
  

cout<<result<<endl;
}

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

int main(){
  int A,B;
  cin >>A>>B;
  if(A==B){
    cout<<"Draw"<<endl;
    return 0;
  }
  if(A==1){
    cout<<"Alice"<<endl;
    return 0;
  }
  if(B==1){
    cout<<"Bob"<<endl;
    return 0;
  }
  if(A-B>0){
    cout<<"Alice"<<endl;
    return 0;
  }
  cout<<"Bob"<<endl;
  return 0;
}


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

int main()
{
    int n;
    scanf(" %d", &n);
    vector<ll> d(n);
    rep(i,n) scanf(" %lld", &d[i]);

    vector<ll> sum(n);
    sum[0]=d[0];
    for(int i=1; i<n; ++i) sum[i]=sum[i-1]+d[i];

    map<ll,int> r;
    rep(i,n) r[sum[i]]=i;

    ll c=0;
    int ans = 0;
    rep(i,n)
    {
        if(r.count(c)) ans = max(ans,r[c]-i+1);
        c += d[i];
    }

    printf("%d\n", ans);
    return 0;
}

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

int main(){
  int n, p, a[50];
  while(cin >> n >> p && n && p){
    for(int k=0;k<n;k++){
      a[k]=0;
    }
    int i, f=p;
    for(i=0;;i=(++i)%n){
      if(p) {
        a[i]++;
        if(a[i]==f) break;
        p--;
      }
      else {
        p += a[i];
        a[i] = 0;
      }
    }
    cout << i << endl;
  }
  return 0;
}

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

long long int countsum(long long int x){
  long long int n = 0;
  for(long long int i = 1; i <= x; i++){
    n+=i;
  }
  return n;
}

int main(){
  string s;
  cin >> s;
  long long int ans = 0;
  long long int sum[500005];
  long long int sum_count = 0;
  long long int count = 1;
  char back = s[0];
  if(s.size()==1){
    cout << 1 << endl;
  }
  else{
  for(long long int i = 1; i < s.size(); i++){
    if(s[i] == back){
      count++;
    }
    else{
      sum[sum_count] = count;
      sum_count++;
      count = 1;
      back = s[i];
    }
    if(i==s.size()-1){
      sum[sum_count] = count;
      sum_count++;
    }
  }
  
  if(s[0] == '<'){
    for(long long int i = 0; i < sum_count+2; i+=2){
      ans += countsum(sum[i]);
      ans += countsum(sum[i+1]);
      ans -= min(sum[i], sum[i+1]);
    }
    cout << ans << endl;
  }
  else{
    ans += countsum(sum[0]);
    for(long long int i = 1; i < sum_count+2; i+=2){
      ans += countsum(sum[i]);
      ans += countsum(sum[i+1]);
      ans -= min(sum[i], sum[i+1]);
    }
    cout << ans << endl;
  }
  }
}


Measured memory_bytes: 4612
//xtwakioi! xtwddYnoi(双重含义)!
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
signed main()
{
    int a,b;
    cin>>a>>b;
    if(a+b<10) printf("%lld\n",a+b);
    else puts("error");
    return 0;
}

Measured memory_bytes: 3672
N, D = map(int, input().split())
X = []
ans = 0
for i in range(N):
  X.append(list(map(int, input().split())))
import math
for i in range(N):
  for j in range(i+1, N):
    lis_1 = X[i]
    lis_2 = X[j]
    cnt = 0
    for k in range(D):
      cnt += (lis_1[k] - lis_2[k]) ** 2
    cnt = math.sqrt(cnt)
    if cnt.is_integer():
      ans += 1
print(ans)

Measured memory_bytes: 9148
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N, M, X, Y = map(int, sys.stdin.readline().split())
    x = list(map(int, sys.stdin.readline().split()))
    y = list(map(int, sys.stdin.readline().split()))
    x.append(X)
    y.append(Y)
    if max(x) >= min(y):
        print("War")
    else:
        print("No War")


Measured memory_bytes: 5072
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=1e9+7;
ll isedge[205][205]={0};
ll h,w;
bool used[205]={0};
ll dfs(ll pos,ll flow){
  if(pos==h+w+1) return flow;
  used[pos]=true;
  for(int i=0;i<=h+w+1;i++){
    if(!used[i]&&isedge[pos][i]>0){
      used[i]=true;
      ll d=dfs(i,min(flow,isedge[pos][i]));
      if(d>0){
        isedge[pos][i]-=d;
        isedge[i][pos]+=d;
        return d;
      }
    }
  }
  return 0;
}
ll cut(ll s,ll t){
  ll ans=0;
  while(1){
    for(int i=0;i<205;i++) used[i]=false;
    ll f=dfs(s,inf);
    if(f==0) return ans;
    ans+=f;
  }
}
int main(){
  cin>>h>>w;
  ll sx,sy,gx,gy;
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      char c;
      cin>>c;
      if(c=='o'){
        isedge[i][j+h]=1;
        isedge[j+h][i]=1;
      }
      else if(c=='S'){
        isedge[0][i]=inf;
        isedge[0][j+h]=inf;
        isedge[i][0]=inf;
        isedge[j+h][0]=inf;
        sx=i;
        sy=j;
      }
      else if(c=='T'){
        isedge[i][h+w+1]=inf;
        isedge[j+h][h+w+1]=inf;
        isedge[h+w+1][i]=inf;
        isedge[h+w+1][j+h]=inf;
        gx=i;
        gy=j;
      }
    }
  }
  if(sx==gx||sy==gy) cout<<-1<<endl;
  else cout<<cut(0,h+w+1)%inf<<endl;
}


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String[] str = in.readLine().split(" ");
			int H = Integer.parseInt(str[0]);
			int W = Integer.parseInt(str[1]);
			if (H == 0 && W == 0)
				break;
			for (int i = 0; i < H; i += 1) {
				for (int j = 0; j < W; j += 1) {
					System.out.print("#");
				}
				System.out.print("\n");
			}
			System.out.print("\n");
		}
	}
}

Measured memory_bytes: 29064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1<<22;
typedef long long ll;
typedef unsigned long long ull;
int data[maxn][21],n,k;
int mem[maxn*2];
char s[maxn];
int mx=1000000000,mxl=0;
void update(int sta,int nums,int len) {
    mem[sta|(1<<len)]+=nums;
    if(mem[sta|(1<<len)]>=k)
        if(mxl<len)mxl=len,mx=sta;
        else if(mxl==len)mx=min(mx,sta);

}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++) {
        scanf("%s",s);//len=2^i
        for(int j=0;j<(1<<i);j++) {
            int tmp=j;
            tmp|=1<<i;
            data[tmp][0]+=(s[j]=='1');
        }
    }
    for(int i=0;i<=n;i++) {//枚举已经拿了多少个
        for(int j=0;j<(1<<(n+1));j++) {//一共有n+1位
            if(!data[j][i])continue;//t-s
            ull s=j&((1<<i)-1),t=j>>i;int l=(32-__builtin_clz(t))-1;//有t多少位
            if(i)update(s,data[j][i],i);
            if(!l){continue;}
            t^=(1<<l);
            int first1=(32-(t?__builtin_clz(t):32));//第一个1在第几位
            unsigned int num=t<<(32-l);
            int first0=l?(l-((~num)?__builtin_clz(~num):l)):0;
            int newt,news;
            if(first1>0){//去掉一个1
                newt=t&((1<<first1)-1);
                newt|=(1<<first1-1);
                news=(s<<1)|1;
                data[(newt<<(i+1))|news][i+1]+=data[j][i];
            }
            if(first0>0){//去掉一个0
                newt=t&((1<<first0)-1);
                newt|=(1<<first0-1);
                news=(s<<1);
                data[(newt<<(i+1))|news][i+1]+=data[j][i];
            }
        }
    }
    if(mx==1000000000){puts("");return 0;}
    for(int i=mxl;i>=1;i--) {
        printf("%d",(mx&(1<<i-1))?1:0);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 185728
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define maxn	500005
#define mod		int(1e9+7)
#define db		double
#define ll		long long
#define si 		stack<int>
#define qi 		queue<int>
#define vi 		vector<int>
#define pi 		pair<int, int>
ll powmod(ll a, ll b) {
	ll res = 1; a %= mod;
	for (; b; b >>= 1)
		res = (res * ((b & 1) ? a : 1)) % mod,
		a = a * a % mod;
	return res;
}
ll gcd(ll a, ll b) {
	return b ? gcd(a, b) : a;
}
int edgenum, head[maxn], vet[2 * maxn], nxt[2 * maxn], a[maxn], b[maxn];
void addedge(int u, int v) {
	edgenum ++;
	vet[edgenum] = v;
	nxt[edgenum] = head[u];
	head[u] = edgenum;
}
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v;
		if(a[u] >= a[v]) b[v] = 1;
		if(a[u] <= a[v]) b[u] = 1;
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) ans += 1 - b[i];
	cout << ans << endl;
	return 0;
}

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

vector<ll> divisor(ll n){
    vector<ll> vec;
    for(ll i=1;i*i<= n;i++){
        if(n%i==0){
            vec.push_back(i);
            if(i*i!=n) vec.push_back(n/i);
        }
    }
    sort(vec.begin(), vec.end());
    return vec;
}

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());

    int cnt = 0;
    if((int)a.size()==1 || a[0]!=a[1]) cnt++;

    for(int i=1;i<n;i++){
        if(i<n-1 && a[i]==a[i+1]) continue;
        
        vector<ll> yak = divisor(a[i]);
        bool ok = true;
        for(int j=0;j<(int)yak.size();j++){
            auto itr = lower_bound(a.begin(),a.begin()+i-1,yak[j]);
            if(*itr==yak[j] && itr!=(a.begin()+i)) ok = false;
        }

        if(ok){
            //cout << "ok: " << i << endl;
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4000
#include "bits/stdc++.h"
#define int long long
#define For(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define Max(x) *max_element(ALL(x))
#define Min(x) *min_element(ALL(x))
#define Lower_bound(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define Upper_bound(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define itn int
#define Endl endl

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

template <class T = int>
int in() {
  T x;
  cin >> x;
  return x;
}
int bpm(int x, int y) {
  if (x == 0)
    return 0;
  else if (y == 0) {
    return 1;
  }
  int ans = 1;
  x %= MOD;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) {
      ans *= x;
      ans %= MOD;
    }
    x = x * x;
    x %= MOD;
  }
  return ans;
}

signed main() {
  int N = in();
  vector<int> a(N);
  int two    = 0;
  int four   = 0;
  int others = 0;
  rep(i, N) {
    cin >> a[i];
    if (a[i] % 4 == 0) {
      four++;
    } else if (a[i] % 2 == 0) {
      two++;
    } else {
      others++;
    }
  }
  if (two == 0) {
    if (four >= N / 2) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
    return 0;
  }
  N -= two;
  if (four >= (N + 1) / 2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 1024
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    int  w, h, n ; 
    cin >> w >> h >> n ; 
    int l=0,r=w,u=h,d=0;
    for (int i=0;i<n;i++){
        int x,y,a;
        cin>>x>>y>>a;
        if (a==1) l=max(l,x);
        if (a==2) r=min(r,x);
        if (a==3) d=max(d,y);
        if (a==4) u=min(u,y);
    }
    cout << (max(r-l,0LL)*max(u-d,0LL)) << endl; 
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
int n, ans, id;
set<int> st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        ans = max(ans, x); st.insert(x);
    }
    set<int>::iterator it = st.lower_bound(ans/ 2);
    if (it != st.end() && *it != ans) id = *it;
    if (it != st.begin()) {
        --it;
        if (min(*it, ans - *it) > min(id, ans - id))
            id = *it;
    }
    printf("%d %d", ans, id);
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

signed main(){
  int n;
  cin>>n;
  int debt=100000;
  rep(i,n){
    debt*=1.05;
    int a=debt%1000;
    if(a)debt+=1000;
    debt-=a;
  }
  cout<<debt<<endl;
  return 0;
}

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


def main():
    K = int(input())
    A, B = map(int, input().split())
    ans = "NG"
    for i in range(A, B+1):
        if i % K == 0:
            ans = "OK"
            break
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9104
#include "bits/stdc++.h"

using namespace std;

//typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)

struct UnionFind {
	vector< int > data;

	UnionFind(int sz) {
		data.assign(sz, -1);
	}

	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return (false);
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return (true);
	}

	int find(int k) {
		if (data[k] < 0) return (k);
		return (data[k] = find(data[k]));
	}

	int size(int k) {
		return (-data[find(k)]);
	}
};

signed main(){

	int N, M;
	cin >> N >> M;
	vector<int> p;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		p.push_back(t);
	}

	UnionFind u(N+1);

	for (int i = 0; i < M; i++){
		int s, t;
		cin >> s >> t;
		u.unite(s, t);
	}
	int ans = 0;
	for (int i = 0; i < N; i++){
		if (u.find(i+1) == u.find(p[i])) ans++;
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1908