akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pllll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll n, k, c;
  cin >> n >> k >> c;
  string s;
  cin >> s;
  vi l, r;
  ll cnt = 0;
  fi(0, n) {
    if(s[i] == 'o') {
      l.push_back(i);
      cnt++;
      if(cnt == k) {
        break;
      }
      i += c;
    }
  }
  
  cnt = 0;
  for(int i = n - 1; i >= 0; i--) {
    if(s[i] == 'o') {
      r.push_back(i);
      cnt++;
      if(cnt == k) {
        break;
      }
      i -= c;
    }
  }
  sort(all(r));
  fi(0, k) {
    if(l[i] == r[i])
      cout << l[i] + 1 << endl;
  }
  return 0;
}



Measured memory_bytes: 3448
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // fixed, setprecision 
#include <math.h> // double sqrt
#define rep(i,n) for(int i=0;i<(n);++i)
#define ll long long
using namespace std;

int main(){
int n,m,x;
cin>>n>>m>>x;
vector<int>a(m);
rep(i,m)cin>>a[i];
int o=0,u=0;
rep(i,m){
    if(a[i]>x)o++;
    if(a[i]<x)u++;
}
cout<<min(o,u);
return 0;

}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


int main() {
    string s,t; cin >> s >> t;

    set<string> st;
    rep(i, s.size()-t.size()+1) {
        bool flag = true;
        rep(j, t.size()) {
            if(s[i+j] == t[j] || s[i+j] == '?') continue;
            else {
                flag = false;
                break;
            }
        }
        if(flag) {
            string tmp = s;
            tmp.replace(i, t.size(), t);
            replace(tmp.begin(), tmp.end(), '?', 'a');
            st.insert(tmp);
        }
    }
    if(st.size() == 0) {
        cout << "UNRESTORABLE" << endl;
    } else {
        cout << *st.begin() << endl;
    }



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
int cnt[100010];
int main() {
  int n,q;
  string s;
  cin >> n >> q >> s;
  int ac = 0;
  rep(i,n-1) {
    if (s[i] == 'A' && s[i+1] == 'C') {
      cnt[i+1] = cnt[i] + 1;
    } 
    else cnt[i+1] = cnt[i];
  }
  rep(i,q) {
    int l,r; cin >> l >> r;
    l--; r--;
   if (l == 0) cout << cnt[r] << endl;
   else cout << cnt[r] -  cnt[l] << endl;
  } 
  return 0;
}

Measured memory_bytes: 4156
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int y,m,d;
ll t;
ll x[4] = {19890108,19261225,19120730,18680908};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin >> y >> m >> d){
		t = 10000*y+100*m+d;
		if(t >= x[0]) cout << "heisei " << y-(x[0]/10000)+1 << " " << m << " " << d << endl;
		else if(t >= x[1]) cout << "showa " << y-(x[1]/10000)+1 << " " << m << " " << d << endl;
		else if(t >= x[2]) cout << "taisho " << y-(x[2]/10000)+1 << " " << m << " " << d << endl;
		else if(t >= x[3]) cout << "meiji " << y-(x[3]/10000)+1 << " " << m << " " << d << endl;
		else cout << "pre-meiji" << endl;
	}
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
#define ll long long int
#define endl '\n'
#define mp make_pair
#define pb push_back
#define mod 1000000007

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	double ans=a[0];
	for(int i=0;i<n;i++)
	{
		ans+=a[i];
		ans/=2;
	}
	cout<<ans;
return 0;
}



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

mod=10**9+7

a1=1
a2=1
a3=1
for i in range(n):
  a1*=10
  a2*=9
  a3*=8
  a1%=mod
  a2%=mod
  a3%=mod

ans=a1-a2-a2+a3
ans%=mod
print(ans)

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

int main(){
    bool cards[4][14];
    int n,rank;
    char suit;
    
    for(int s=0;s<4;s++)
     for(int r=1;r<=13;r++)
      cards[s][r] =0;
      
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> suit >> rank;
        if(suit == 'S')cards[0][rank]=1;
        if(suit == 'H')cards[1][rank]=1;
        if(suit == 'C')cards[2][rank]=1;
        if(suit == 'D')cards[3][rank]=1;
    }
    for (int s=0;s<4;s++){
        for (int r=1;r<=13;r++){
            if(cards[s][r])continue;
            if(s==0)suit='S';
            if(s==1)suit='H';
            if(s==2)suit='C';
            if(s==3)suit='D';
            cout << suit << " " << r << endl;
        }
    }
    
    return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll x,y,z;
  cin>>x>>y>>z;
  swap(x,y);
  swap(x,z);
  cout<<x << " " << y << " " << z << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;
#define REP(i,j,n) for(int i=j;i<n;i++)
#define rep(i,n) REP(i,0,n)


// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int x=0;
    rep(i, s.length())
    {
        x += (int)(s[i]-'0');
        x%=9;
    }
    if (x==0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int h,w;
  cin >> h >>w;
  vector<string>a(h);
  for(int i =0;i<h;i++){
    string s;
    cin >> s;
    a.at(i) =s;
  }
  for(int i = 0;i<w+2;i++){
    cout << '#';
  }
  cout << endl;
  for(int i=0;i<h;i++){
   cout << '#' << a.at(i) <<'#'<< endl;
  }
    for(int i = 0;i<w+2;i++){
    cout << '#';
  }
}

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

int main() {
    long long int x, a, b,f=0,a1,b1;
    a=-120;
    cin>>x;
    while(a<120){
        b=-120;
        while(b<120){
            if(pow(a,5)-pow(b,5)==x){
                f=1;
                a1=a;
                b1=b;
                break;
            }
            b++;
        }
        a++;
        if(f==1)
            break;
    }
    cout<<a1<<" "<<b1<<"\n";
    return 0;
}


Measured memory_bytes: 3988
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  string a;
  cin>>a;
  char b=1;
  int c=0;
  rep(i,a.size()){
  if(b!=a[i]){
    c++;
  b=a[i];
  }
    else{
      if(i!=a.size()-1){
      c++;
    i++;
      b=1;
      }
    }
  }
  out(c);
}


Measured memory_bytes: 3816
# ABC078a
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

x, y = input()[:-1].split()
alphabet = list('abcdefghijklmnopqrstuvwxyz'.upper())

if alphabet.index(x) < alphabet.index(y):
    print('<')
elif x == y:
    print('=')
else:
    print('>')


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(a,j,n) for(ll i=a;i<j;i=i+n )
typedef pair<ll,ll> P;
const ll mod = 1000000007;
const ll INF = 1000000009;
ll i;


int main(){
    ll N;
    cin>>N;
    V A(N);
    rep(0,N,1)cin>>A.at(i);
    bool jud=true;
    rep(0,N,1){
        if(A.at(i)%2==0&&A.at(i)%3!=0&&A.at(i)%5!=0){
            jud=false;
            break;
        }
    }
    if(jud)cout<<"APPROVED";
    else cout<<"DENIED";
    cout<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int in;
  int h,m,s;
  scanf("%d",&in);

  h = in / 3600;
  in %= 3600;

  m = in / 60;
  in %= 60;

  s = in;

  printf("%d:%d:%d\n",h,m,s);
}

Measured memory_bytes: 2720
#define  _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#pragma comment (linker, "/STACK:526000000")

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(10);
}

#define int ll

void solve() {
	int n;
	cin >> n;
	vector<int> inputs;
	REP(i, n) {
		int a;
		cin >> a;
		inputs.push_back(a);
	}
	for (int q = 0;; ++q) {
		string s = to_string(q);
		int bobo = 0;
		for (int j = 0; j < inputs.size() - s.length()+1; ++j) {
			int ok = 1;
			REP(q, s.length()) {
				if (s[q] != inputs[j + q] + '0') {
					ok = 0;
				}
			}
			if (ok == 1) {
				bobo = 1;
			}
		}
		if (bobo == 0) {
			cout << q << endl;
			return;
		}
	}
}
#undef int

int main() {
	init();
	solve();
}


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

int main(){
  int x, y, z;
  char komma;
  int hishi, choho;

  hishi=0; choho=0;
  while(cin>>x>>komma>>y>>komma>>z){
    if(x==y && x+y>z) hishi++;
    else if(x*x+y*y==z*z) choho++;
  }
  printf("%d\n%d\n", choho, hishi);

  return 0;
}

Measured memory_bytes: 0
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let _n: usize = input();
    let k: usize = input();
    let mut s: Vec<char> = input::<String>().chars().collect();
    if s[k - 1] == 'A' {
        s[k - 1] = 'a';
    } else if s[k - 1] == 'B' {
        s[k - 1] = 'b';
    } else {
        s[k - 1] = 'c';
    }
    println!("{}", s.iter().cloned().collect::<String>());
}


Measured memory_bytes: 4352
t,e,i,j,a=-1,x,i;main(n){for(scanf("%d%d%d",&n,&t,&e);i++<n;)for(scanf("%d",&x),j=x;j<=t+e;j+=x)j-e<=t&&j+e>=t?a=i:0;printf("%d\n",a);exit(0);}

Measured memory_bytes: 596
n = int(input())
s = [input() for i in range(n)]
j = ['AC', 'WA', 'TLE', 'RE']
l = [0]*len(j)
for i in s:
    for m in range(len(j)):
        if i == j[m]:
            l[m] += 1
            
for i in range(len(j)):
    print(j[i] + ' x ' + str(l[i]))

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

int vaccation(int A[], int B[], int C[], int n)
{
    int dp[n+1][3];

    dp[1][0] = A[1];
    dp[1][1] = B[1];
    dp[1][2] = C[1];

    for(int i=2; i<=n; i++)
    {
        dp[i][0] = A[i] + max(dp[i-1][1],dp[i-1][2]);
        dp[i][1] = B[i] + max(dp[i-1][0],dp[i-1][2]);
        dp[i][2] = C[i] + max(dp[i-1][0],dp[i-1][1]);
    }

    int ans = max(dp[n][0], max(dp[n][1], dp[n][2]));

    return ans;
}

int main() 
{
    int n;
    cin>>n;

    int A[n+1], B[n+1], C[n+1];

    for(int i=1; i<=n; i++)
        cin>>A[i]>>B[i]>>C[i];

    cout<<vaccation(A,B,C,n)<<endl;

    return 0;
}


Measured memory_bytes: 5852
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  bool r0[n];
  memset(r0, 0x00, n);
  int r1[n];
  int nr1 = 0;
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (a > b) {
      int t = a;
      a = b;
      b = t;
    }
    if (a == 1) r0[b - 1] = true;
    if (b == n) r1[nr1++] = a - 1;
  }
  bool res = false;
  for (int i = 0; i < nr1; i++) {
    if (r0[r1[i]]) res = true;
  }
  puts(res ? "POSSIBLE" : "IMPOSSIBLE");
  return 0;
}


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

int main(){
  long long n, k;
  cin >> n >> k;
  if(k % 2 == 0){
    long long countModZero = 0;
    long long countModHalf = 0;
    for(int i=1; i<=n; i++){
      if(i % k == 0) countModZero++;
      if(i % k == k/2) countModHalf++;
    }
    cout << countModZero*countModZero*countModZero + countModHalf*countModHalf*countModHalf << endl;
  }else{
    long long countModZero = 0;
    for(int i=1; i<=n; i++){
      if(i % k == 0) countModZero++;
    }
    cout << countModZero*countModZero*countModZero << endl;
  }
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second

void Max(int &x, int y) {
    if (x < y) x = y;
}

void Min(int &x, int y) {
    if (x > y) x = y;
}


int fa[200010], cnt[200010];

int findfa(int x) {
    return x == fa[x] ? x: fa[x] = findfa(fa[x]);
}

void gao(int x, int y) {
    int u = findfa(x), v = findfa(y);
    if (u != v) {
        fa[u] = v;
        cnt[v] += cnt[u];
    }
}

int main(void) {

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n + m; ++ i) fa[i] = i;
    for (int i = 1; i <= n; ++ i) cnt[i] = 1;
    for (int i = 1; i <= n; ++ i) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; ++ j) {
            int lj;
            cin >> lj;
            gao(i, lj + n);
        }
    }

 //   for (int i = 1; i <= n; ++ i) {
//        cout << i << ' ' << findfa(i) << ' ' << cnt[findfa(i)] << endl;
  //  }

    int x = findfa(1);
    if (cnt[x] == n) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

Measured memory_bytes: 1792
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
res = 0
for i in range(1,n+1):
    if i%3 and i%5:
        res += i
print(res)


Measured memory_bytes: 10480
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//ABC131D
void swap(int *a, int *b) {
  int temp=*a;
  *a=*b, *b=temp;
}
//二つの配列を連動させてソート
void QuickSort(int A[], int B[], int left, int right) { //クイックソート//
  int Left=left, Right=right, pivot=A[(left + right) / 2];
  while(1){ // ソーティング
    while(A[Left] < pivot)
      Left++; // 基準より小さい値を左から見つけていく
    while(pivot < A[Right])
      Right--; // 基準より大きい値を右から見つけていく
    if(Left >= Right) break; // 見つかった値の順序が逆になったら終了
    swap(&A[Left], &A[Right]); // 値を交換
    swap(&B[Left], &B[Right]);
    Left++, Right--; // 次の値に移動
  }
  if(left < Left - 1) QuickSort(A, B, left, Left - 1); //左群を対象として再帰
  if(Right + 1 < right) QuickSort(A, B, Right + 1, right); //右群を対象として再帰
}
int main(void) {
  int n, k, i, sum=0, tmp;
  scanf("%d", &n);
  int a[n], b[n];
  for(i=0; i < n; i++){
    scanf(" %d %d", &a[i], &b[i]);
  }
  QuickSort(b, a, 0, n - 1);
  for(i=0; i < n; i++){
    sum+=a[i];
    //printf("%d %d\n",sum,b[i]);
    if(sum > b[i]){
      printf("No");
      return 0;
    }
  }
  printf("Yes");
  return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
int main() {
   int N,D;
   int X=0;
   cin >> N >> D;
   for(int i=0; i < N; i++){
     double p,q;
     cin >> p >> q;
     if (sqrt(p*p+q*q) <= D){
       X++;
     }
   }
  cout << X << endl;
}

Measured memory_bytes: 3808
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int a,b;
  while(1){
    cin>>a>>b;
    int dp[20][20]={};
    if(a==0&&b==0)break;
    int n;
    cin>>n;
    rep(i,n){
      int x,y;
      cin>>x>>y;
      x--;y--;
      dp[x][y]--;
    }
    dp[0][0]++;

    rep(i,a)rep(j,b)
      if(i==0 && j==0)
        continue;
      else if(dp[i][j]<0)
        continue;
      else if(i==0)
        dp[i][j]=max(0,dp[i][j-1]);
      else if(j==0)
        dp[i][j]=max(0,dp[i-1][j]);
      else
        dp[i][j]=max(0,dp[i][j-1])+max(0,dp[i-1][j]);

    cout<<dp[a-1][b-1]<<endl;
  }
}

Measured memory_bytes: 3068
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <array>
using namespace std;

int main() {
    array<array<int, 2>, 4> dm = {{
        { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 },
    }};
    array<array<int, 2>, 25> dw = {{
        { -2, -2 }, { -2, -1 }, { -2, 0 }, { -2, 1 }, { -2, 2 },
        { -1, -2 }, { -1, -1 }, { -1, 0 }, { -1, 1 }, { -1, 2 },
        { 0, -2 }, { 0, -1 }, { 0, 0 }, { 0, 1 }, { 0, 2 },
        { 1, -2 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 1, 2 },
        { 2, -2 }, { 2, -1 }, { 2, 0 }, { 2, 1 }, { 2, 2 },
    }};

    int h, w; cin >> h >> w;
    array<int, 2> c; cin >> c[0] >> c[1];
    array<int, 2> d; cin >> d[0] >> d[1];
    for (auto &e : c) --e;
    for (auto &e : d) --e;
    vector<string> field(h);
    for (auto &e : field) cin >> e;

    int cidx = 0, didx = -1;
    vector<vector<int>> g;

    vector<vector<bool>> visited(h, vector<bool>(w, false));
    queue<array<int, 3>> warpable;
    warpable.push({ c[0], c[1], -1 });

    while (!warpable.empty()) {
        auto [wy, wx, from] = warpable.front(); warpable.pop();
        if (visited[wy][wx]) continue;
        visited[wy][wx] = true;

        int nidx = g.size();
        g.emplace_back();

        if (from != -1) {
            g[from].push_back(nidx);
            g[nidx].push_back(from);
        }

        if (wy == d[0] && wx == d[1]) {
            didx = nidx;
        }

        queue<array<int, 2>> que;
        que.push({ wy, wx });

        while (!que.empty()) {
            auto [cy, cx] = que.front(); que.pop();

            for (auto [dy, dx] : dm) {
                int ny = cy + dy, nx = cx + dx;
                if (ny < 0 || nx < 0 || h <= ny || w <= nx) continue;
                if (field[ny][nx] == '#' || visited[ny][nx]) continue;
                visited[ny][nx] = true;

                if (ny == d[0] && nx == d[1]) {
                    didx = nidx;
                }

                que.push({ ny, nx });
            }

            for (auto [dy, dx] : dw) {
                int ny = cy + dy, nx = cx + dx;
                if (ny < 0 || nx < 0 || h <= ny || w <= nx) continue;
                if (field[ny][nx] == '#' || visited[ny][nx]) continue;
                warpable.push({ ny, nx, nidx });
            }
        }
    }

    if (didx < 0) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> cost(g.size(), -1);
    queue<int> que;

    cost[cidx] = 0;
    que.push(cidx);

    while (!que.empty()) {
        auto cur = que.front(); que.pop();

        for (auto e : g[cur]) {
            if (cost[e] != -1) continue;
            cost[e] = cost[cur] + 1;
            que.push(e);
        }
    }

    cout << cost[didx] << endl;
}



Measured memory_bytes: 15500
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int MOD = 1000000007;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		sc.close();
		long sum=0;
		for (i = 1; i <= n; i++) {
			if(i%3==0||i%5==0) continue;
			sum+=i;
		}
		out.println(sum);
	}
}


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

int main() {
    int x, tmp, ans;
    cin >> x ;

    tmp = 0;
    ans = 0;
    //xずつ足していき, % 360が0になった時のカウンタを返す
    while (1) {
        tmp = tmp + x;
        ans += 1;
        if (tmp % 360 == 0) {
            cout << ans << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3632
import itertools

A = range(int(input())+1)
B = range(int(input())+1)
C = range(int(input())+1)
X = int(input())

ans = 0
for coins in itertools.product(A, B, C):
    if (coins[0]*500+coins[1]*100+coins[2]*50) == X:
        ans += 1

print(ans)

Measured memory_bytes: 9168
#include<stdio.h>
int main(void){
    char s[4];
    scanf("%s",s);
    if(s[0]=='S'&&s[1]=='U'){
        printf("7\n");
    }else{
        if(s[0]=='M'){
            printf("6\n");
        }else{
            if(s[0]=='T'&&s[1]=='U'){
                printf("5\n");
            }else{
                if(s[0]=='W'){
                    printf("4\n");
                }else{
                    if(s[0]=='T'){
                        printf("3\n");
                    }else{
                        if(s[0]=='F'){
                            printf("2\n");
                        }else{
                            if(s[0]=='S'){
                                printf("1\n");
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
  return modpow(a, mod - 2, mod);
}

//                123456789
const ll kMod = 1000000007;

int main() {
  const ll INV2 = modinv(2, kMod);
  
  ll N, K;
  cin >> N >> K;
  ll ans = 0;
  for (ll i = K; i <= N + 1; ++i) {
    //ll mn = i * (i - 1) / 2;
    ll mn = i * (i - 1) % kMod * INV2 % kMod;
      
    //ll mx = i * (2 * N - i + 1) / 2;
    ll tmp = (2 * N % kMod - i + 1 + kMod) % kMod;
    ll mx = i * tmp % kMod * INV2 % kMod;
    
    // ans += mx - mn + 1;
    ll tmp2 = (mx - mn + 1 + kMod) % kMod;
    ans = (ans + tmp2) % kMod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3152
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

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

void solve() {
	string s;
	cin >> s;
	stack<char> ret;
	int ans = 0;
	for(int i = 0; i < s.size(); i++) {
		if(ret.size() && ret.top() != s[i]) {
			ret.pop();
			ans += 2;
		}
		else {
			ret.push(s[i]);
		}
	}
	cout << ans << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}


Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, m, bo[100009], po[100009];
vector<pair<int, int> > vec;
vector<long long> ans;

int fun0(int x)
{
	if (bo[x] != x) bo[x] = fun0(bo[x]);
	return bo[x];
}

void fun1(int x, int y)
{
	if (fun0(x) < fun0(y)) {
		po[bo[x]] += po[bo[y]];
		bo[bo[y]] = bo[x];
	}
	else {
		po[bo[y]] += po[bo[x]];
		bo[bo[x]] = bo[y];
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		bo[i] = i;
		po[i] = 1;
	}
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec.pb(make_pair(t1, t2));
	}
	reverse(vec.begin(), vec.end());
	long long cur = n * 1LL * (n - 1) / 2;
	ans.pb(cur);
	for (int i = 0; i < m - 1; i++) {
		int u = vec[i].fi, v = vec[i].se;
		if (fun0(u) == fun0(v)) {
			ans.pb(cur);
			continue;
		}
		cur -= po[bo[u]] * 1LL * po[bo[v]];
		fun1(u, v);
		ans.pb(cur);
	}
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << "\n";
	//system("pause");
	return 0;
}

Measured memory_bytes: 3828
n, m = map(int, input().split())
from collections import defaultdict

g1 = defaultdict(set)
g2 = defaultdict(set)

for _ in range(m):
    s, t = map(int, input().split())
    g1[s].add(t)
    g2[t].add(s)

p = defaultdict(int)
p[1] = 1

for i in range(1, n + 1):
    for j in g1[i]:
        p[j] += p[i]/len(g1[i])

e = defaultdict(int)
for i in range(n, 0, -1):
    for j in g1[i]:
        e[i] += (e[j] + 1) / len(g1[i])
ans = e[1]

for i in range(n, 0, -1):
    ne = 0
    if len(g1[i]) == 1:
        continue
    for j in g1[i]:
        ne += (e[j] + 1) / (len(g1[i]) - 1)

    for j in g1[i]:
        dis = ne - (e[j] + 1) / (len(g1[i]) - 1) - e[i]
        ans = min(ans,e[1] + p[i]*dis)

print(ans)

Measured memory_bytes: 78808
import math
n,m = map(int,input().split())
MAX = m//n
ans = 1
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
a = divisor(m)
for i in a:
  if i <= MAX:
    ans = i
print(int(ans))

Measured memory_bytes: 39664
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
    //int array[] = null;
    Scanner scan = new Scanner(System.in);
    String str = scan.nextLine();
    int n = new Integer(str);
    int array[] = new int[n];

    int right = 0;
    int left = 0;

    if(n % 2 == 0){
    right = n/2;
    left = right - 1;
  } else{
    right = n/2 + 1;
    left = right - 1;
  }

    str = scan.nextLine();
    String str2[] = str.split(" ");

    for(int i = 0; i < n; i++){
      if(i % 2 == 0){
        array[left--] = new Integer(str2[i]);
      } else{
        array[right++] = new Integer(str2[i]);
      }
    }

    if(array.length % 2 != 0){
    for(int i = 0; i < array.length; i++){
      System.out.print(array[i] + " ");
    }
  } else {
    for(int i = array.length - 1; i >= 0; i--){
      System.out.print(array[i] + " ");
    }
  }
    System.out.println();
  }
}


Measured memory_bytes: 74244
import copy

h,w = map(int, input().split())
list_a = []
for i in range(0,h):
    list_a.append(list(str(input())))

list_check = copy.deepcopy(list_a)
for i in range(0,h):
    for j in range(0,w):
        list_a[i][j] = "."

i = 0
j = 0
while True:
    if i == h-1 and j == w-1:
        list_a[i][j] = "#"
        break
    if list_check[i][j] == "#":
        list_a[i][j] = "#"
        if i != h-1:
            i += 1
        else:
            j += 1
    else:
        i -= 1
        j += 1
        if j > w-1:
            ans = "Impossible"
            break
        if list_check[i][j] == ".":
            ans = "Impossible"
            break
if list_a == list_check:
    ans = "Possible"
else:
    ans = "Impossible"
print(ans)


Measured memory_bytes: 3956
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;

#define rep(i, N) for (ll i = 0; i < (ll)(N); ++i)
#define ALL(a) (a).begin(),(a).end()

const ll inf = 1e18+7;
const ll mod = 1e9+7;

int main(){
	float N,M,sum=0,ab=0,ans=0;
	cin >>N>>M;
	vector<ll> A(N,0);
	rep(i,N){
	 cin >> A[i];
	 sum += A[i];
	}
	ab=sum/(4*M);
	for(ll i=0;i<N;i++){
		if(A[i]>=ab){
			ans++;
		}
	}
	if(ans>=M){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;
 
using namespace std;
 
/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MX = 100010;
 
bitset<MX> b;
bitset<MX> fr;
bitset<MX> go;
int dd[MX];
queue<int> qu;
 
int main() {
	int k;
	cin >> k;
	if (k == 1) {
		cout << 1 << "\n";
		return 0;
	}
	ll cur = 1;
	while (true) {
		if (b[cur])
			break;
		b[cur] = 1;
		cur = (cur * 10) % k;
	}
	for (int i = 0; i < k; ++i) {
		dd[i] = 100000;
	}
	for (int i = 0; i < k; ++i) {
		if (b[i]) {
			dd[i] = 1;
			qu.push(i);
		}
		else
			fr[i] = 1;
	}
	while (!qu.empty()) {
		int x = qu.front();
		if (x == 0) {
			cout << dd[x] << "\n";
			return 0;
		}
		qu.pop();
		go = (b << x) | (b >> (k - x));
		go &= fr;
		while (go.any()) {
			int y = go._Find_first();
			go[y] = 0;
			dd[y] = dd[x] + 1;
			fr[y] = 0;
			qu.push(y);
		}
	}
	return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

typedef long long ll;

struct Cups{
	std::vector<int> S[3];
	int t, prev_from, prev_to;
	Cups(const std::vector<int> (&_S)[3], int _t, int _from, int _to)
		:t(_t), prev_from(_from), prev_to(_to)
	{
		for(int i=0;i<3;i++){
			S[i] = _S[i];
		}
	}
};

int main(){
	int n, m;
	while(std::cin >> n >> m, n){
		std::vector<int> S[3];
		for(int i=0;i<3;i++){
			int SN;
			std::cin >> SN;
			for(int j=0;j<SN;j++){
				int e;
				std::cin >> e;
				S[i].push_back(e-1);
			}
			std::sort(S[i].begin(), S[i].end(), std::greater<int>());
		}

		std::queue<Cups> q;
		q.push(Cups(S, 0, -1, -1));
	
		int res = -1;
		while(!q.empty()){
			Cups c = q.front();q.pop();
			std::vector<int> S[3] = c.S;
			int t = c.t, prev_from = c.prev_from, prev_to = c.prev_to;

			if(t > m){
				continue;
			}
			if(S[0].size() == n || S[2].size() == n){
				res = t;
				break;
			}

			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){//i -> j
					if(std::abs(i-j) != 1 || (j == prev_from && i == prev_to) ||
						 S[i].empty() || (!S[j].empty() && S[i][0] < S[j][0]))continue;
					std::vector<int> _S[3] = S;
					_S[j].push_back(_S[i][0]);
					_S[i].erase(_S[i].begin());
					std::sort(_S[j].begin(), _S[j].end(), std::greater<int>());
					q.push(Cups(_S, t+1, i, j));
				}
			}
		}

		std::cout << res << std::endl;
	}
}

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

ll digSum(ll i){
	ll sum=0;
	while(i){
		sum+=i%10;
		i/=10;
	}
	return sum;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	ll n, a, b;
	cin >> n >> a >> b;
	ll sum=0, buf;
	for(ll i=1;i<=n;i++){
		buf = digSum(i);
		if(buf>=a&&buf<=b)
			sum+=i;
	}
	cout << sum << "\n";
	return 0;
}


Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as B
import Data.List (unfoldr)
import Data.Char (isSpace)

readInt = B.readInt . B.dropWhile isSpace

main = do
  n <- read <$> getLine
  as <- take n . unfoldr readInt <$> B.getLine
  print $ sum as - (n :: Int)

Measured memory_bytes: 1020
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
ll dp[60][60][60][60];
ll ans[51] = { 0,
1,
2,
12,
84,
770,
8340,
106400,
1546888,
25343766,
461133960,
232367169,
627905865,
632459808,
928262728,
919805769,
382796331,
887217496,
639768068,
869694124,
205875097,
205589953,
487772376,
239955313,
998339621,
31622834,
902930073,
146839084,
449786840,
982224660,
865803735,
21834818,
721531716,
26008837,
471774471,
69010090,
700009308,
776938882,
645550477,
526939604,
142728157,
654489641,
128201240,
185493259,
789721045,
977049419,
589149550,
700648836,
25087729,
874433491,
352791804
};
int main()
{
	int num;
	scanf("%d", &num);
	printf("%lld\n", ans[num]);
	/*invinit();
	dp[num][0][0][0] = 1;
	for (int i = num - 1; i >= 0; i--)
	{
		for (int j = 0; j <= num; j++)
		{
			for (int k = 0; k <= j; k++)
			{
				for (int l = 0; l <= j - k; l++)
				{
					if (dp[i + 1][j][k][l] == 0)continue;
					for (int m = 0; m <= num - j; m++)
					{
						for (int n = 0; n <= num - j - m; n++)
						{
							if (k - l > n || l - k > m)continue;
							if (k + l > 0 && m + n == 0)continue;
							dp[i][j + m + n][m - l + k][n - k + l] = (dp[i][j + m + n][m - l + k][n - k + l] + dp[i + 1][j][k][l] * com(j + m, m) % mod*com(j + m + n, n)) % mod;
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 50;i++)printf("%lld,\n", dp[0][i][1][0]);*/
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(sm))

Measured memory_bytes: 20012
#include<cstdio>
using namespace std;
#define N 23
int dp[1<<N][N],n,k,v[N],nt[N][2],ct,le,lg[1<<N];
char s[1<<N];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<=n;i++)
	{
		scanf("%s",s);
		for(int j=0;j<1<<i;j++)
		dp[j|(1<<i)][0]=s[j]=='1';
	}
	for(int i=2;i<1<<n+1;i++)lg[i]=lg[i>>1]+1;
	for(int j=(1<<n+1)-1;j>=0;j--)
	{
		int le=lg[j];
		for(int k=1;k<=le;k++)v[k]=(bool)(j&(1<<k-1));
		nt[le][0]=nt[le][1]=-1;
		for(int k=le-1;k>=0;k--)
		{
			nt[k][0]=nt[k+1][0];nt[k][1]=nt[k+1][1];
			nt[k][v[k+1]]=k+1;
		}
		for(int k=0;k<=le;k++)
		if(dp[j][k])
		{
			dp[j&((1<<k)-1)][k+1]=dp[j&((1<<k)-1)][k+1]+dp[j][k];
			if(nt[k][0]!=-1)dp[(j&((1<<k)-1))|(j>>(nt[k][0]-1)<<k)][k+1]=dp[(j&((1<<k)-1))|(j>>(nt[k][0]-1)<<k)][k+1]+dp[j][k];
			if(nt[k][1]!=-1)dp[(j&((1<<k)-1))|(j>>(nt[k][1]-1)<<k)][k+1]=dp[(j&((1<<k)-1))|(j>>(nt[k][1]-1)<<k)][k+1]+dp[j][k];
		}
	}
	for(int l=n;l>=1;l--)
	for(int j=0;j<1<<l;j++)
	if(dp[j][l+1]>=k)
	{
		for(int i=l;i>=1;i--)printf("%d",(bool)(j&(1<<i-1)));
		return 0;
	}
}

Measured memory_bytes: 201984
object Main {
  def main(args: Array[String]): Unit = {
    val candidate_num = scala.io.StdIn.readInt
    val temperatures  = scala.io.StdIn.readLine.split(" ").map{_.toInt}
    val candidate     = scala.io.StdIn.readLine.split(" ").map{_.toInt}
    var diff_min      = 100000.0
    var dicision_num  = 0

    for(i <- 0 until candidate.length) {
      val diff = Math.abs(temperatures(1) - (temperatures(0) - 0.006*candidate(i)))
      if (diff_min > diff) {
        diff_min     = diff
        dicision_num = i + 1
      }
    }
    println(dicision_num)
  }
}

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

int N, cnt[610][610];

void fill(int d){
	int a=1, b=d;
	while(b%4==0){
		a *= 2;
		b /= 4;
	}
	for(int i=0; i<N*2; ++i){
		for(int j=0; j<N*2; ++j){
			if(b%4==3) ++cnt[i][j];
			else if(b%4==1 && (i/a+j/a)%2==0) ++cnt[i][j];
			else if(b%4==2 && (i/a)%2==0) ++cnt[i][j];
		}
	}
}

int main() {
	int D1, D2;
	cin >> N >> D1 >> D2;
	fill(D1);
	fill(D2);
	int sum=0;
	for(int i=0; i<N*2; ++i){
		for(int j=0; j<N*2; ++j){
			if(cnt[i][j]==2){
				cout << i << ' ' << j << endl;
				++sum;
				if(sum==N*N) return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2304
import sys
from itertools import combinations 
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
M = int(input())
uv = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
pathnum = {}
for n,(a,b) in enumerate(ab):
    g[a].append(b)
    g[b].append(a)
    a,b = sorted([a,b])
    pathnum[(a,b)] = n

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    vtour = []
    etour = []
    depth = [-1]*(n+1)
    parent = [False]*(n+1)
    visited = [False]*(n+1)
    def dfs(v,d):
        depth[v] = d
        visited[v] = True
        ls[v] = len(vtour)
        vtour.append(v)
        etour.append(v)
        for nv in g[v]:
            if not visited[nv]:
                parent[nv] = v
                dfs(nv,d+1)
        rs[v] = len(vtour)
        etour.append(-v)
        vtour.append(parent[v])
    dfs(s,0)
    return ls,rs,etour,vtour,parent,depth

ls,rs,etour,vtour,parent,depth = eulerTour(g,1)
paths = []
depthind = [depth[v] for v in vtour]

for u,v in uv:
    l,r = ls[u],ls[v]
    l,r = (l,r) if l < r else (r,l)
    lcaind = depthind[l:r].index(min(depthind[l:r]))
    lca = vtour[l+lcaind]
    lpath = []
    x = u
    while x != lca:
        lpath.append(pathnum[tuple(sorted((x,parent[x])))])
        x = parent[x]
    rpath = []
    x = v
    while x != lca:
        rpath.append(pathnum[tuple(sorted((x,parent[x])))])
        x = parent[x]
    path = set(lpath + rpath)
    h = sum([1<<i for i in path])
    paths.append(h)
    
ans = 2**(N-1)

memo = {1<<i:paths[i] for i in range(M)}
memo[0] = 0
for i in range(1,M+1):
    for vs in combinations(list(range(M)),i):
        sign = i % 2
        h = sum([1<<i for i in vs])
        ph = h ^ (1<<vs[-1])
        sect = memo[ph] | paths[vs[-1]]
        memo[h] = sect
        num = N-1 - str(bin(sect)).count('1')
        ans += (-1)**sign * (2**num)

print(ans)






Measured memory_bytes: 131700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(v) (v).begin(),(v).end()

int main() {

	int N;
	cin >> N;
	V<> L(N);
	REP(i, N) cin >> L[i];

	sort(ALL(L));
	int ans = 0;
	// REP(i, N) cout << L[i] << " \n"[i==N-1];
	for(int i=0; i<N-2; i++) {
		int a = L[i];
		for(int j=i+1; j<N-1; j++) {
			int b = L[j];
			ans += upper_bound(L.begin()+j+1, L.end(), a+b-1) - (L.begin()+j+1);
			// cout << *upper_bound(L.begin()+j, L.end(), a+b) << endl;
			// cout << upper_bound(L.begin()+j, L.end(), a+b) - (L.begin()+j) << endl;
		}
	}

	cout << ans << endl;
}

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

int main() {

	char* S = new char[200001];
	char* T = new char[200001];
	cin >> S >> T;

	char* s = S;
	char* t = T;
	int c = 0;
	while (*s != '\0') {
		if (*s != *t) {
			c++;
		}
		s++;
		t++;
	}
	cout << c << endl;
	return(0);
}


Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

int main()
{
#define MAX 3000
    vector<ll> v(MAX+1);
    map<ll, ll> m;
    for (ll n = 0; n <= MAX; n++) {
        v[n] = n*n*n*n*n;
        m[v[n]] = n;
    }
    ll X; cin >> X;

    for (int i = 0; i < v.size(); i++) {
        ll a5 = v[i];
        ll b5 = a5 - X;
        ll abs_b5 = abs(b5);
        if (m.count(abs_b5) > 0) {
            ll a = i;
            ll b = b5 > 0 ? m[abs_b5] : -m[abs_b5];
            cout << a << " " << b << endl;
            return 0;
        }
        a5 = -a5;
        b5 = a5 - X;
        abs_b5 = abs(b5);
        if (m.count(abs_b5) > 0) {
            ll a = -i;
            ll b = -m[abs_b5];
            cout << a << " " << b << endl;
            return 0;
        }
    }


    int ans = 0;

    cout << ans << endl;
}


Measured memory_bytes: 3840
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define MOD 1000000007

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> vr, vl;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        stack<char> st;
        for (int j = 0; j < s.length(); j++)
        {
            if (s[j] == '(')
            {
                st.push('(');
            }
            else
            {
                if (st.empty())
                {
                    st.push(')');
                }
                else if (st.top() == '(')
                {
                    st.pop();
                }
                else
                {
                    st.push(')');
                }
            }
        }
        int lpcnt = 0, rpcnt = 0;
        while (!st.empty())
        {
            char c = st.top();
            st.pop();
            if (c == '(')
                lpcnt++;
            else
                rpcnt++;
        }
        if (lpcnt - rpcnt >= 0)
            vl.push_back(make_pair(rpcnt, lpcnt));
        else
            vr.push_back(make_pair(lpcnt, rpcnt));
    }
    sort(vl.begin(), vl.end());
    sort(vr.begin(), vr.end());
    reverse(vr.begin(), vr.end());
    int tmp = 0;
    for (int i = 0; i < vl.size(); i++)
    {
        tmp -= vl[i].first;
        if (tmp < 0)
        {
            cout << "No" << endl;
            return 0;
        }
        tmp += vl[i].second;
    }
    for (int i = 0; i < vr.size(); i++)
    {
        tmp -= vr[i].second;
        if (tmp < 0)
        {
            cout << "No" << endl;
            return 0;
        }
        tmp += vr[i].first;
    }
    if (tmp == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 11188