akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim(){
    int u, minv, i;
    int d[MAX], q[MAX], color[MAX];
    
    for ( i = 0; i < n; i++ ) {
        d[i] = INFTY;
        q[i] = -1;
        color[i] = WHITE;
    }
    
    d[0] = 0;
    
    while ( 1 ){
        minv = INFTY;
        u = -1;
        for ( int i = 0; i < n; i ++ ){
            if ( minv > d[i] && color[i] != BLACK ){
                u = i;
                minv =d[i];
            }
        }
        if ( u == -1 ) break;
        color[u] = BLACK;
        for ( int v = 0; v < n; v++ ){
            if ( color[v] != BLACK && M[u][v] != INFTY){
                if ( d[v] > M[u][v] ){
                    d[v] = M[u][v];
                    q[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for ( int i = 0; i < n; i++ ){
        if( q[i] != -1 ) sum += M[i][q[i]];
    }
    
    return sum;
}

int main() {
    cin >> n;
    
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            int e; cin >> e;
            M[i][j] = ( e == -1 ) ? INFTY : e;
        }
    }
    
    cout << prim() << endl;
    
    return 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

using Grid = vector<string>;

int H, W, K;
Grid v;

Grid remove_cell(Grid const& in, int y, int x) {
  auto result = in;
  result[y][x] = '-';
  return result;
}

Grid drop(Grid const& in) {
  vector<stack<char>> stks(W);
  rep(i, H) rep(j, W) {
    if (in[i][j] != '-') {
      stks[j].push(in[i][j]);
    }
  }

  Grid result(H);
  rep(i, H) result[i].resize(W, '-');
  rep(j, W) rep(i, H) {
    if (!stks[j].empty()) {
      auto cell = stks[j].top();
      stks[j].pop();
      result[H - i - 1][j] = cell;      
    } else {
      result[H - i - 1][j] = '-';
    }
  }
  return result;
}

string remove_right_forward_in_line(string const& in, int sj) {
  auto work = in;
  const auto rmchar = in[sj];
  REP(j, sj, W) {
    if (work[j] != rmchar) { break; }
    work[j] = '-';
  }
  return work;
}

Grid remove_connected_cells(Grid const& in) {
  auto work = in;
  rep(i, H) rep(j, W - K + 1) {
    if (work[i][j] == '-') { continue; }
    auto s = work[i].substr(j, K);
    s.erase(std::unique(s.begin(), s.end()), s.end());
    if (s.size() == 1) {
      work[i] = remove_right_forward_in_line(work[i], j);
    }
  }
  return work;
}

int calc_sum(Grid const& in) {
  int sum = 0;
  rep(i, H) rep(j, W) {
    sum += in[i][j] == '-' ? 0 : (in[i][j] - '0');
  }
  return sum;
}

int solve(Grid work) {
  int score = 0;
  for (int pexp = 0; ; pexp++) {
    auto next_work = drop(remove_connected_cells(work));
    auto diff = calc_sum(work) - calc_sum(next_work);
    if (diff == 0) { break; }
    score += (1 << pexp) * diff;
    work = next_work;
  }
  return score;
}

int solve() {
  int max_score = 0;
  rep(i, H) rep(j, W) {
    maximize(max_score, solve(drop(remove_cell(v, i, j))));
  }
  return max_score;
}

int main() {
  cin >> H >> W >> K;
  v.resize(H); cin >> v;
  cout << solve() << "\n";
}


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

using namespace std;
using namespace __gnu_cxx;


#define ll long long
const long double EPS = 1e-8;
const long double PI = acos(-1);
const int N = 1e5 + 9;
const ll inf = (ll) -1e18;
const int mod = 1e9 + 7;
typedef vector<vector<ll>> Mat;

vector<pair<int, int>> dir = {{-1, -1},
                              {-1, 0},
                              {-1, 1},
                              {0,  -1},
                              {0,  1},
                              {1,  -1},
                              {1,  0},
                              {1,  1}};

struct Mul {
    int sz = 1;

    Mat operator()(const Mat &a, const Mat &b) const {
        Mat ret(a.size(), vector<ll>(b[0].size()));
        for (int i = 0; i < ret.size(); i++) {//row in first matrix
            for (int j = 0; j < ret[0].size(); j++) {//col in second matrix
                for (int k = 0; k < b.size(); k++) {
                    ret[i][j] = (ret[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
                }
            }
        }
        return ret;
    }
};

Mat identity_element(const Mul &mul) {
    Mat ret(mul.sz, vector<ll>(mul.sz));
    for (int i = 0; i < mul.sz; i++)ret[i][i] = 1;
    return ret;
}

int main() {
//    freopen("input.txt", "r", stdin);
    int t;
//    scanf("%d", &t);
//    while (t--) {
    int n;
    ll k;
    scanf("%d%lld", &n, &k);
    Mat v(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%lld", &v[i][j]);
        }
    }
    Mul multiplyOperator;
    multiplyOperator.sz = n * n;

    Mat ans = power(v, k, multiplyOperator);
    ll a = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a = (a + ans[i][j]) % mod;
        }
    }
    printf("%lld\n", a);
//    }

}

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

using namespace std;

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

    int n,k;
    cin>>n>>k;
    vector<pair<int,long long> >v(n);
    for(int i=0;i<n;i++)
        cin>>v[i].first>>v[i].second;
    int tmk=k;
    int msk=0;
    int imsk=0;
    while(tmk){
        msk|=(1<<imsk);
        imsk++;
        tmk>>=1;
    }
    long long bst=-1ll;
    long long ttl=0ll;
    for(int i=0;i<n;i++){
        if((v[i].first|k)==k)
            ttl+=v[i].second;
    }
    bst=max(bst,ttl);
    for(int i=imsk-1;i>=0;i--){
        ttl=0ll;
        if(k&(1<<i)){
            int nmsk=msk^(1<<i);
            for(int j=0;j<n;j++){
                 if((v[j].first|nmsk)==nmsk)
                    ttl+=v[j].second;
            }
            bst=max(bst,ttl);
        }else{
            msk^=(1<<i);
        }
    }
    cout<<bst<<'\n';
    return 0;
}
/***
3 5
3 3
4 4
2 5
*/


Measured memory_bytes: 4784
#include<stdio.h>
#include<string.h>

int main()
{
  char s[100] = "";
  char x = 'x';
  int i = 0;
  
  scanf( "%s",s);
  while(s[i] != '\0')
  {
    s[i] = x;
    i++;
  }

  printf("%s",s);
    return 0;
}

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

int main() {
    int64_t N;
    cin >> N;

    int64_t X = 1;
    int64_t Y = 1;
    int64_t Z = 1;

    for (int i = 0; i < N; i++) {
        X = X * 10;
        Y = Y * 9;
        Z = Z * 8;
        if (Z >= 1000000007) {
            X = X % 1000000007;
            Y = Y % 1000000007;
            Z = Z % 1000000007;            
        }
    }

    if (X + Z - 2 * Y < 0) {
        X = X + 1000000007;
        Z = Z + 1000000007;
    }

    cout << (X + Z - 2 * Y) % 1000000007 << endl;
}


Measured memory_bytes: 3632
#include<iostream>

using namespace std;

int main()
{
	int n, q;
	int S[10001], T[500];
	int count = 0;
        cin >> n;
	for( int i = 0; i < n; i++ )
	{
		cin >> S[i];
	}
	cin >> q;
	for( int i = 0; i < q; i++ )
	{
		cin >> T[i];
	}

	for( int i = 0; i < q; i++ )
	{
		S[n] = T[i];
		int j = 0;
		while( S[j] != T[i] )
		{
			j++;
		}
		count += ( j != n );
	}
	cout << count << endl;
	return 0;

}

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

int main(){
  long long n,a,b;
  cin>>n>>a>>b;
  long long cycle = a+b;
  long long ret = (n/cycle)*a;
  n%=cycle;
  if(n<a) ret+=n;
  else ret+=a;
  cout<<ret;
}
  

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

int main() {
    int h, w, a, b; cin >> h >> w >> a >> b;
    string s = string(a, '0') + string(w-a, '1');
    string t = string(a, '1') + string(w-a, '0');
    for (int i = 0; i < b; i++) {
        cout << s << "\n";
    }
    for (int i = 0; i < h-b; i++) {
        cout << t << "\n";
    }
    return 0;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<int,int> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

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


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

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

    ll ans=0;
    ll c_b=0;
    REP(i,s.size()){
        if(s[i]=='B') c_b++;
        else ans += c_b;
    }

    pl(ans)

    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <utility>
#include <queue>

using namespace std;

typedef pair<int, int> P;
typedef pair<P, P> RAT;

const int INF = 100000000;

char map[1005][1005];
int flag[1005][1005];
int H,W,N;
int cheese;
int sx,sy;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main()
{
	queue<RAT> que;
	int tx,ty;
	scanf("%d %d %d",&H,&W,&N);
	for(int i=0;i<H;i++)
	{
		scanf("%s",map[i]);
		for(int j=0;j<W;j++)
			if(map[i][j] == 'S')
			{
				sx = i;
				sy = j;
			}
	}
	
	que.push(RAT(P(sx,sy),P(1,0)));
	cheese = 1;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			flag[i][j] = INF;
	for(;;)
	{
		RAT rat = que.front();
		que.pop();
		if(rat.second.first == N+1)
		{
			printf("%d\n",rat.second.second);
			break;
		}
		if(cheese > rat.second.first)
			continue;
		if(cheese < rat.second.first)
		{
			cheese = rat.second.first;
			for(int i=0;i<H;i++)
				for(int j=0;j<W;j++)
					flag[i][j] = INF;
		}
		for(int i=0;i<4;i++)
		{
			tx = rat.first.first + dx[i];
			ty = rat.first.second + dy[i];
			if(tx >= 0 && tx < H && ty >= 0 && ty < W && map[tx][ty] != 'X' && flag[tx][ty] != 0)
			{
				if(rat.second.first == map[tx][ty]-48)
				{
					que.push(RAT(P(tx,ty),P(rat.second.first+1,rat.second.second+1)));
					flag[tx][ty] = 0;
				}
				else
				{
					que.push(RAT(P(tx,ty),P(rat.second.first,rat.second.second+1)));
					flag[tx][ty] = 0;
				}
			}
		}
	}
	return 0;	
}

Measured memory_bytes: 5980
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner scan = new Scanner(System.in);
	    int x = scan.nextInt();
		int y = scan.nextInt();
		int m = x * y;
		int s = (x+y)*2;
		System.out.println(m + " "+ s);
	}

}

Measured memory_bytes: 26320
N=int(input())
*H,=map(int,input().split())

for i in range(-1,-len(H),-1):
   #print(i,H[i],H[i-1])
   if H[i]<H[i-1]-1:
    print('No')
    break
   if H[i-1]-1 == H[i]:
    H[i-1]=H[i]
else:
   print('Yes')

Measured memory_bytes: 20648
#include <stdio.h>

int main(void)
{
	int a;
	int b;
	
	scanf("%d %d", &a, &b);
	
	if (a < b){
		printf("a < b\n");
	}
	else if (a > b){
		printf("a > b\n");
	}
	else if (a == b){
		printf("a == b\n");
	}
	
	return 0;
}

Measured memory_bytes: 580
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int main(void)
{
    //input
    int N=0, M=0;
    cin>>N>>M;

    int K[N];
    int A[N][M];
    for(int i=0; i<N; i++)
    {
        cin>>K[i];
        for(int j=0; j<K[i]; j++)
        {
            cin>>A[i][j];
        }
    }
    
    //calc
    int NUM = M;
    bool ariv;
    for(int a=1; a<=M; a++)
    {
        for(int i=0; i<N; i++)
        {
            ariv = false;
            for(int j=0; j<K[i]; j++)
            {
                if(a==A[i][j]) ariv = true;
            }
            if(!ariv) 
            {
                NUM--;
                break;
            } 
        }
    }

    //output
    cout<<NUM;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000000007
#define ll long long int
ll fac[100001];
ll inv(ll n){
  ll ans=1;
  n%=MAX;
  ll p=MAX-2;
  while(p>0){
    if(p%2==1) {p--;ans=(ans*n)%MAX;}
    p/=2;
    n=(n*n)%MAX;
    ans%=MAX;
  }
  return(ans);
}
ll fact(ll n){
  fac[0]=1;
  for(ll i=1;i<=n;i++) fac[i]=(i*fac[i-1])%MAX;
}
ll ncr(ll n,ll r){
  return(((fac[n] * inv(fac[r]))%MAX * inv(fac[n-r]))%MAX);
}
int main(){
  ll n,k,sum=0;
  cin>>n>>k;
  ll a[n+1];
  for(int i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+n+1);
  fact(n);
  for(int i=1;i<=n;i++){
    if(i>=k) sum=(sum+a[i]*ncr(i-1,k-1))%MAX;
    if(i+k-1<=n) sum=(sum-a[i]*ncr(n-i,k-1))%MAX;
    sum=(sum+MAX)%MAX;
  }
  cout<<sum%MAX;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

string s;
int main()
{
unsigned long long k;
cin >> s;
cin >> k;
char ans = '1';
for(int i = 0; i<k; ++i)
{
    if (s[i] != '1')
    {
        ans = s[i];
        break;
    }
}

cout << ans << endl;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>



using namespace std;


int main()
{
	int year;
	cin >> year;
	if (year < 1000)
	{
		cout << "ABC\n";
		return 0;
	}
	cout << "ABD\n";
	return 0;
}


Measured memory_bytes: 256
/*Made by Shivam Solanki*/
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define ll long long int
#define endl '\n'
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<pii> vp;
typedef vector<pll> vpll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> sii;
typedef set<ll> sll;
typedef queue<int> qii;
typedef priority_queue<int> pq;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll,ll> umll;
#define all(x) x.begin(),x.end()
#define rep(i,k,n) for (int i = k; i < n; ++i) 
#define repr(i,k,n) for (int i = n; i>=k; --i)
#define repll(i,k,n) for (ll i = k; i < n; ++i) 
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int INF = 1e9+5;
const int MOD = 1e9+7;

void solve(){
    int n;
    cin>>n;
    ll sum=0;
    rep(i,1,n+1){
        rep(j,1,n+1){
            rep(k,1,n+1){
                sum+=gcd(i,gcd(j,k));
            }
        }
    }
    cout<<sum;
}

int main(){ 
    // #ifndef ONLINE_JUDGE  
        // freopen("input.txt", "r", stdin); 
        // freopen("output.txt", "w", stdout); 
    // #endif 
    fastio;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
    return 0;
}


Measured memory_bytes: 3556
#include <iostream>

int main(){
  int n,count=0;
  std::cin >> n;
  int a[n];
  for(int i=0; i<n; i++){
    std::cin >> a[i];
  }
  
  for(int i=0; i<n; i+=2){
    if(a[i]%2 == 1){count++;}
  }
  
  std::cout << count << std::endl;
  
  return 0;
}


Measured memory_bytes: 3628
function Main(input) {
input = input.split("\n");
aa = input[0].split(" ");
  
var x = aa[0].split(" ");
var y = aa[1].split(" ");

var tu = ( 4 * x - y ) / ( 4 - 2 )
var ka = x - tu
 if  ( ka >= 0 && tu >= 0 && Number.isInteger ( ka ) == true) {
  var result = "Yes";
 } else {
  var result = "No";
 }

console.log(result);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));





Measured memory_bytes: 29632
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

struct IoSetup {
#define endl '\n'
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        // cout << fixed << setprecision(20);
        // cerr << fixed << setprecision(20);
    }
} iosetup;

template <class Info>
struct edge {
    int from, to;
    Info info;
    edge(int to, Info info) : to(to), info(info) {}
    edge(int from, int to, Info info) : from(from), to(to), info(info) {}
};

struct normal_edge {
    normal_edge() {}
};

//! graphは基本クラス！使うときはundirected_graphかdirected_graphを使う。
template <class Info>
class graph {
   protected:
    using edge_type = edge<Info>;
    ::std::size_t N;
    ::std::vector<::std::vector<edge_type>> edges;

   public:
    graph(::std::size_t N_) : N(N_), edges(N_) {}
    virtual void add_edge(int x, int y, Info info = static_cast<Info>(1)) = 0;
    const ::std::vector<edge_type> &delta(int v) const {
        assert(v < N);
        return edges[v];
    }
    const ::std::vector<edge_type> &operator[](int v) const {
        return this->delta(v);
    }
    ::std::size_t size() const { return N; }
};

template <class Info>
class undirected_graph : public graph<Info> {
   public:
    undirected_graph(::std::size_t N) : graph<Info>(N) {}
    void add_edge(int x, int y, Info info = static_cast<Info>(1)) {
        this->edges[x].push_back(edge<Info>(x, y, info));
        this->edges[y].push_back(edge<Info>(y, x, info));
    }
};

template <class Info>
class directed_graph : public graph<Info> {
   public:
    directed_graph(::std::size_t N) : graph<Info>(N) {}
    void add_edge(int x, int y, Info info = static_cast<Info>(1)) {
        this->edges[x].push_back(edge<Info>(x, y, info));
    }
};

template <class Info>
class bipartite_graph : public undirected_graph<Info> {
    ::std::size_t A;
    ::std::size_t B;

   public:
    bipartite_graph(::std::size_t A_, ::std::size_t B_)
        : A(A_), B(B_), undirected_graph<Info>(A_ + B_) {}
    void add_edge(int x, int y, Info info = static_cast<Info>(1)) {
        undirected_graph<Info>::add_edge(x, y + A, info);
    }
};

void solve() {
    i64 N, M;
    cin >> N >> M;
    directed_graph<i64> g(3 * N);
    while(M--) {
        i64 u, v;
        cin >> u >> v;
        u--, v--;
        g.add_edge(u, v + N);
        g.add_edge(u + N, v + 2 * N);
        g.add_edge(u + 2 * N, v);
    }
    i64 S, T;
    cin >> S >> T;
    S--, T--;
    vector<i64> dist(3 * N, -1);
    queue<i64> q;
    q.push(S);
    dist[S] = 0;
    while(!q.empty()) {
        i64 v = q.front();
        q.pop();
        for(auto e : g[v]) {
            if(dist[e.to] != -1) continue;
            dist[e.to] = dist[e.from] + e.info;
            q.push(e.to);
        }
    }
    cout << (dist[T] == -1 ? -1 : dist[T] / 3) << endl;
};

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

Measured memory_bytes: 19072
#include"bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define double long double
#define int long long
#define pb push_back 
#define Z(c) (int)(c).size()
#define L(c) c[Z(c)-1]
#define F first
#define S second
#define nl "\n"
#define mii map<int,int> 
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define rep(i,iv,n) for(int (i)=(iv);(i)<(n);++(i))
#define FO fflush(stdout) 
#define D1(x) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<nl
#define D2(x,y) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<nl
#define D3(x,y,z) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<nl
#define tr(it,ct) for(auto &(it) : (ct))
#define pi acos(-1)
#define prt(ct) for(auto &(it) : (ct)) cerr<<it<<" "; cerr<<nl
#define prtp(ct) for(auto &(it) : (ct)) cerr<<it.F<<" "<<it.S<<nl; cerr<<nl

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > pii;
typedef vector< pii > vp;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> baap;

void swap(char &a,char &b)
{ auto tm=a; a=b; b=tm; }

void mina(int &a,int b)
{ a=(a<b?a:b); }

void maxa(int &a,int b)
{ a=(a>b?a:b); }

  const int mod=1000000007;
  const int mod2=998244353;
  const int INF=1e16+18;
  const int N=1e5+15;
  const int M=3e3+13;
  
 double dp[M][M];

 void fft()    
 {
   int n; cin>>n;
  
   dp[0][0]=1;

   for(int i=1;i<=n;++i){
       double x;  cin>>x;
      for(int j=0;j<=i;++j){

           if(j)
           dp[i][j]=dp[i-1][j-1]*x;

           dp[i][j]+=dp[i-1][j]*(1-x);

   //      cerr<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<nl;
      }
   }

   double ans=0;

   
   for(int i=n/2+1;i<=n;++i) ans+=dp[n][i];

   cout<<setprecision(10)<<ans;

 }

signed main()
{ 
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                  
   int tc=1;                         
 //  cin>>tc;

  rep(i,1,tc+1)
  { // cout<<"Case #"<<i<<": ";
   fft();
   if(i<tc)
   cout<<nl;
  }
  
 return 0; 
}

Measured memory_bytes: 139776
N = [int(_) for _ in input().split()][0]

e = [0] * (N + 1)

for i in range(2, N + 1):
    tmp = i
    for j in range(2, i + 1):
        if tmp <= 1: break
        while tmp % j == 0:
            e[j] += 1
            tmp //= j

dp = [[0] * 76 for _ in range(N + 1)]

dp[0][1] = 1
for i in range(1, N + 1):
    for j in range(e[i] + 1):  # i番目を j個使う
        for k in range(75 + 1):
            if k * (j + 1) > 75: break
            if dp[i - 1][k] > 0:
                dp[i][k * (j + 1)] += dp[i - 1][k]

# for i in range(len(dp)):
#     print(dp[i])
print(dp[N][75])


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

using namespace std;

const int MAXN = 1e5 + 10;
class Edges{
public:
	int next , to;
};
Edges edge[MAXN * 2];
int first[MAXN];
int n , k , x;
int ans = 0 , te = 0;
void add(int s , int t){
	++ te;
	edge[te].next = first[s];
	edge[te].to = t;
	first[s] = te;
}

int set(int pos , int fa){
	int maxn = 1;
	for(int e = first[pos] ; e ; e = edge[e].next){
		int to = edge[e].to;
		if(to == fa) continue;
		maxn = max(maxn , set(to , pos) + 1);
	}
	if(maxn == k && fa != 1){
		ans ++;
		return 0;
	}
	else
		return maxn;
}
int main(){
	cin >> n >> k >> x;
	if(x != 1) ans ++;
	for(int i = 2 ; i <= n ; ++ i){
		cin >> x;
		add(x , i);
		add(i , x);
	}
	set(1 , 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6912
#include <stdio.h>

int main(void){
  int s, m, h;
  scanf("%d", &s);

  h = s / 3600;
  m = (s % 3600) / 60;
  s = s % 60;

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



Measured memory_bytes: 1988
N = int(input())
# white: 0, black: 1
g = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    g[u-1].append((v-1, w))
    g[v-1].append((u-1, w))

visited = [False]*N
from collections import deque

q = deque()
q.append([0, 0])
while q:
    num, kyori = q.pop()
    visited[num] = '1' if kyori%2 == 1 else '0'
    for hen in g[num]:
        if not visited[hen[0]]:
            q.append([hen[0], kyori+hen[1]]) 

print('\n'.join(visited))

Measured memory_bytes: 68772
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
 
int main() {
  int a;
  string s;
  cin >> a >> s;
  
  if(a>=3200)cout << s << endl;
  else cout << "red" << endl;
}



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

using namespace std;
typedef long long ll;

int main(){
    double A, B, H, M, ans;

    cin >> A >> B >> H >> M;

    ans = A*A + B*B - 2.0e0*A*B*cos( ((H*60.0e0 + M)/720.0e0 - M/60.0e0)*2.0e0*M_PI );

    cout << setprecision(12) << sqrt(ans) << endl;
    // printf("%20.20Lf\n", sqrtl(ans));


    return 0;
}

Measured memory_bytes: 4188
#include <iostream>

using namespace std;

int calc(int (&x)[5])
{
    for (int i = 0; i < 5; i++)
    {
        if (x[i] == 0)
        {
            return i + 1;
        }
    }

    return -1;
}

int main()
{
    int x[5];
    for (int i = 0; i < 5; i++)
    {
        cin >> x[i];
    }

    int answer = calc(x);

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 3524
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,d=0;
    string sr;

    cin>>sr;
    b=(sr[0]- '0')*10+(sr[1]-'0');
    c=(sr[2]- '0')*10+(sr[3]-'0');
   // cout<<b<<" "<<c<<endl;
    if(b>=1&&b<=12&&c>=1&&c<=12)
        cout<<"AMBIGUOUS";
    else if(b>=1&&b<=12)
        cout<<"MMYY";
    else if(c>=1&&c<=12)
        cout<<"YYMM";
    else
        cout<<"NA";


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int64_t i=0;i<(int64_t)N;i++)
const int INF=0x7f7f7f7f;
int main()
{
  int N,M,X,check,cost,pay=INF;
  cin>>N>>M>>X;
  vector<int> C(N,0),up(M,0);
  vector<vector<int>> A(N,vector<int>(M,0));
  rep(i,N){cin>>C.at(i);rep(j,M)cin>>A.at(i).at(j);}
  rep(i,(1<<N))
  {
    cost=0;rep(k,M)up.at(k)=0;
    rep(j,N)
    {
      if((i>>j)%2)
      {
        cost+=C.at(j);check=1;
        rep(k,M){up.at(k)+=A.at(j).at(k);check&=((up.at(k)<X)?0:1);}
        if(check)pay=(cost<pay)?cost:pay;
      }
    }
  }
  return printf("%d\n",(pay==INF)?-1:pay),0;
}

Measured memory_bytes: 3708
// In The Name Of Allah
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e12;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
const ll mod = 1e9 + 7;
 
void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll M = 300 + 10;
const ll N = 200 * 1000 + 10;

ll a[M], dp[2][N];
int n;

ll solve(int t, int k)
{
	if(k == 0)
		return dp[t][k] = 0;
	if(dp[t][k] != -1)
		return dp[t][k];
	dp[t][k] = 0;
	for (int i = 0; i < n; i++)
	{
		if(k < a[i])
			break;
		dp[t][k] = max(1 - solve(1 - t, k - a[i]), dp[t][k]);
	}
	return dp[t][k];
}

int main()	
{
	faster();
	ll k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i <= k + 10; i++)
	{
		for (int j = 0; j < 2; j++)
			dp[j][i] = -1;
	}
	if(solve(0, k))
		cout << "First\n";
	else
		cout << "Second\n";
}

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

int main() {
  
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++){
    int l, r, x;
    cin >> l >> r;
    
    x = r - l + 1;
    
    int sum;
    sum = sum + x;
    
    if (i == N - 1){
    cout << sum << endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define cin_fit() cin.tie(nullptr);ios::sync_with_stdio(false)
#define rep(i, N) for(int i=0; i<(N); i++)
#define reps(i, N) for(int i=1; i<=(N); i++)
#define rrep(i, N) for(int i=(int)(N)-1; i>=0; i--)
#define rreps(i, N) for(int i=(int)(N); i>=1; i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
using namespace std;
using ll = long long;
using V = vector<ll>;
using P = pair<ll, ll>;
constexpr int mod = 1e9+7;

ll n;

int main() {
    cin >> n;
    V a(n);
    rep(i, n) cin >> a[i];

    V b(n), c(n);
    b[0] = a[0], c[n-1] = a[n-1];
    reps(i, n-1) b[i] = __gcd(b[i-1], a[i]);
    rrep(i, n-1) c[i] = __gcd(c[i+1], a[i]);

    ll ret = max(b[n-2], c[1]); // 端を消したとき
    for(int i=1; i<n-1; i++) ret = max(ret, __gcd(b[i-1], c[i+1]));
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 2560
/*BISMILLAHIR RAHMANIR RAHIM*/
#include <bits/stdc++.h>
using namespace std;
#define ll              long long
#define pb              push_back
#define all(x)          x.begin(), x.end()
#define all(y)          y.begin(), y.end()
#define all(z)          z.begin(), z.end()
#define pi              acos(-1.0)

int main()
{
    string str;
    getline(cin, str);
    if(str[0] >= 'A' && str[0] <= 'Z')
    {
        cout << 'A' << endl;
    }
    else cout << 'a' << endl;
}
/*ALHAMDULILLAH*/


Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
	int fn, sn, tn, t1n, t2n, a;
	float ft, st, tt, t1t, t2t, b;
	
	t1t = t2t = 100;
	t1n = t2n = 0;
	for(int i = 0; i < 3; i++){
		fn = sn = tn = 0;
		ft = st = tt = 1000;
		for(int j = 0; j < 8; j++){
			cin >> a >> b;
			if(b < ft){
				tt = st;
				tn = sn;
				st = ft;
				sn = fn;
				ft = b;
				fn = a;
			} else if(b < st){
				tt = st;
				tn = sn;
				st = b;
				sn = a;
			} else if(b < tt){
				tt = b;
				tn = a;
			}
		}
		cout << fn << " " << ft << endl;
		cout << sn << " " << st << endl;
		if(tt < t1t){
			t2t = t1t;
			t2n = t1n;
			t1t = tt;
			t1n = tn;
		} else if(tt < t2t){
			t2t = tt;
			t2n = tn;
		}
	}
	cout << t1n << " " << t1t << endl;
	cout << t2n << " " << t2t << endl;
	
	return 0;
}

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

using namespace std;

int main(int argc, char *argv[])
{
    int N;
    cin >> N;

    vector<int> A;
    vector<int> B;
    vector<int> C;

    for(int i = 0; i < N; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
    }

//    10 40 70
//    20 50 80
//    30 60 90

//    10  40  70
//    90  120 120
//    180 210 180

//    10 40 70
//    90 120 120
//    150 180 210

//    6 7 8
//    8 8 3
//    2 5 2
//    7 8 6
//    4 6 8
//    2 3 4
//    7 5 1

//    6  7   8
//    15 16 10
//    18 20 18
//    27 26 26
//    30 33 35
//    37 38 38
//    45 43 39

//    6         7        8
//  b 14      a 15    b 16
//  b 19    a,c 17    b 21
//  b 27     a  24    b 29
//  c 35     c  32    b 35
//  c 39     c  36    b 38
//  b 44     a  43    b 45


//        c b c b a b a




    vector<vector<int>> dp(N, vector<int>(3, 0));
    dp[0] = {A[0], B[0], C[0]};

    for(int i = 1; i < N; i++)
    {
//        dp[i][0] = dp[i-1][0] + max(B[i], C[i]);
//        dp[i][1] = dp[i-1][1] + max(A[i], C[i]);
//        dp[i][2] = dp[i-1][2] + max(A[i], B[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]);
    }

    cout << max({dp[N-1][0], dp[N-1][1], dp[N-1][2]}) << endl;

    return 0;
}


Measured memory_bytes: 6892
def divider(A,N):
    """
    リストA内の全要素が全て2**nで割れるときTrueを返す
    """
    cnt_list=[]
    same=True
    for n in range(N):        
        tmp=A[n]
        cnt=0
        while tmp%2==0:
            tmp//=2
            cnt+=1
        cnt_list.append(cnt)
        if n>=1 and cnt!=cnt_list[n-1]:
            same=False
            break
    return same       

def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    max_A=max(A)

    if divider(A,N)==False:
        no_ans=True
        minX=0
    else:
        fin=False
        no_ans=False
        i=0
        while fin==False:
            coef=2*i+1
            if max_A*coef>M:
                fin=True
                no_ans=True
            else:
                hit=True
                for n in range(N):
                    if max_A*coef%A[n]==0:
                        if (max_A*coef//A[n])%2==1:
                            pass
                        else:
                            hit=False
                            break
                    else:
                        hit=False
                        break

                if hit==False:
                    i+=1
                else:
                    fin=True
        minX=max_A*coef
    return no_ans,minX

def main():
    #input
    N,M=map(int,input().strip().split())
    A=list(map(int,input().strip().split()))
    A=list(map(lambda x:x//2,A))
    
    #題意を満たす最小のXを求める。
    no_ans,minX=cal_minX(A,N,M)
    #1-Mの中にminXの奇数倍数がいくつあるか調べる
    if no_ans:
        return 0
    else:
        if M//minX%2==1:
            return M//minX//2+1
        else:
            return M//minX//2
if __name__=="__main__":
    print(main())

Measured memory_bytes: 14292
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll,vector<ll>,greater<ll>> SMALLPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
ll inf=100000000007;
const int mod=1000000007;
void chmin(auto &a,auto b){if(b<a)a=b;}
void chmax(auto &a,auto b){if(a<b)a=b;}
int main(){
  ll n,p,sum=0,ans=0;cin>>n>>p;
  vi v(n);
  rep(i,n){
    cin>>v[i];
    sum+=v[i];
  }
  sort(all(v));
  vi a;
  REP(i,1,sqrt(sum)+1){
    if(sum%i==0){
      a.push_back(i);
      a.push_back(sum/i);
    }
  }
  sort(all(a));
  reverse(all(a));
  for(ll x:a){
    vi b(n);
    rep(i,n)b[i]=v[i]%x;
    sort(all(b));
    int l=0,r=n-1;
    ll k=0;
    bool t=true,u=false;
    while(true){
      if(l==r)u=true;
      if(b[r]==x)r--;
      if(l==r)u=true;
      while(b[l]==0){
        l++;
        if(l==r){
          u=true;
          break;
        }
      }
      if(k>p){
        t=false;
        break;
      }
      if(u)break;
      if(b[l]+b[r]<=x){
        b[r]+=b[l];
        k+=b[l];
        b[l]=0;
        l++;
      }
      else{
        k+=x-b[r];
        b[l]-=x-b[r];
        b[r]=x;
      }
    }
    if(t){
      ans=x;
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define NFOR(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); --i)
#define rep(i, a) for (ll i = 0; i < a; i++)
#define endl "\n"
#define fi first
#define se second
#define MOD 1000000007
#define inf 1e12
#define pb push_back
#define Case cout<<"Case #"<<++cas<<": ";
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}

const int maxn = 305;

double dp[maxn][maxn][maxn];

void solve() {
	ll mod = 1000000007;
	ll n;
	cin >> n;
	vl cnt(4, 0);
	rep(i, n) {
		ll temp;
		cin >> temp;
		cnt[temp]++;
	}

	rep(c, cnt[3] + 1)
		rep(b, n + 1)
			rep(a, n + 1) {
				if (a + b + c > n) continue;

				ll em = n - (a + b + c);
				dp[a][b][c] = 0;
				if (a)
					dp[a][b][c] = dp[a - 1][b][c] * (1.0 * a) / (1.0 * n);
				if (b)
					dp[a][b][c] += dp[a + 1][b - 1][c] * (1.0 * b) / (1.0 * n);
				if (c)
					dp[a][b][c] += dp[a][b + 1][c - 1] * (1.0 * c) / (1.0 * n);

				if (a + b + c > 0)
					dp[a][b][c] += 1;
				if (em < n)
					dp[a][b][c] /= 1 - (1.0 * em) / (1.0 * n);
			}

	cout << setprecision(10) << fixed << dp[cnt[1]][cnt[2]][cnt[3]] << endl;
}

int main()
{
    fastio;
    ll t  = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}


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

typedef long long ll;
typedef std::pair<int, int> P;
using namespace std;

struct edge{int to,cost;};

int n,m;
vector<edge> c[1005];
vector<edge> t[1005];
int d[1005];

void dt(int s){
	fill(d,d+1005,INT_MAX/2);
	priority_queue<P, vector<P>, greater<P> > que;
	d[s] = 0;	
	que.push(P(0,s));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for (int i = 0;i < t[v].size();i++){
			edge e = t[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

void dc(int s){
	fill(d,d+1005,INT_MAX/2);
	priority_queue<P, vector<P>, greater<P> > que;
	d[s] = 0;	
	que.push(P(0,s));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for (int i = 0;i < c[v].size();i++){
			edge e = c[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}


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

	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		for (int i = 0;i < 1005;i++){
			c[i] = vector<edge>(0);
			t[i] = vector<edge>(0);
		}
		int t1,t2,t3,t4;
		for (int i = 0;i < n;i++){
			cin >> t1 >> t2 >> t3 >> t4;
			c[t1].push_back((edge){t2,t3});
			t[t1].push_back((edge){t2,t4});
			c[t2].push_back((edge){t1,t3});
			t[t2].push_back((edge){t1,t4});
		}

		int k;
		cin >> k;

		for (int i = 0;i < k;i++){
			int p,q,r; cin >> p >> q >> r;
			if(r == 1) dt(p);
			else dc(p);
			cout << d[q] << endl;
		}
	}

	return 0;

}



Measured memory_bytes: 3336
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll MOD = 1000000007;
using namespace std;

int main(){
    int n, cnt=0; cin >> n;
    int num[100000] = {0};
    REP(i, n){
        int a; cin >> a;
        num[a-1]++;
    }
    REP(i, 100000){
        if(num[i]) cnt++;
    }
    cout << (cnt%2 ? cnt : cnt-1) << endl;
    return 0;
    
}


Measured memory_bytes: 768
#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
struct node{
	int l,r,id;
}Q[200005],a[200005];
int ans[200005],n,m,q;
bool cmp(node a,node b) {
	return a.r<b.r;
}
int tree[200005];
#define low(x) (x&-x)
inline int ask(int x) {
	int res=0;
	for(;x;x-=low(x))
		res+=tree[x];
	return res;
}
inline void add(int x,int v) {
	for(;x<=n;x+=low(x))
		tree[x]+=v;
}
int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&a[i].l,&a[i].r);
	std::sort(a+1,a+m+1,cmp);
	for(int i=1;i<=q;i++)
		scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	std::sort(Q+1,Q+q+1,cmp);
	int j=1;
	for(int i=1;i<=q;i++) {
		while(j<=m&&a[j].r<=Q[i].r) {
			add(a[j].l,1); j++;
		}
		ans[Q[i].id]=ask(Q[i].r)-ask(Q[i].l-1);
	}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
}

Measured memory_bytes: 5888
from bisect import bisect_left, bisect_right

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]



N, M, *I = map(int, open(0).read().split())
AB, LR = I[:2 * N], I[2 * N:]

A, B = map(list, zip(*sorted(zip(*[iter(AB)] * 2))))
D = [B[0]] + [l ^ r for l, r in zip(B, B[1:])] + [B[-1]]
E = [set() for _ in range(N + 1)]

uf = UnionFind(N + 1)
for i, (l, r) in enumerate(zip(*[iter(LR)] * 2), 1):
    li = bisect_left(A, l)
    ri = bisect_right(A, r)
    if li == ri or uf.same(li, ri):
        continue

    uf.union(li, ri)
    E[li].add((ri, i))
    E[ri].add((li, i))


used = set()
def dfs(v, p):
    res = D[v]
    for u, c in E[v]:
        if u == p:
            continue
        ret = dfs(u, v)
        if ret == 1:
            used.add(c)
        D[u] = 0
        res ^= ret
    return res

for v in range(N + 1):
    if D[v]:
        D[v] = dfs(v, -1)

if sum(D) == 0:
    print(len(used))
    print(*sorted(used))
else:
    print(-1)

Measured memory_bytes: 81020
#include <iostream>
using  namespace std;
int main()
{
	int n,m,j;
	cin>>n>>m;
	if(m%n){
		j=m/n;
		for(int i=j;i>=1;i--)
		{
			if(m%i==0)
			{
				cout<<i<<endl;
				break;
			}
		}
	}
	else
		cout<<m/n<<endl;
	return 0;
}


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

int main() {
  int x,n;
  cin >> x >> n;
  vector<int> p(n);
  rep(i,n) {
    cin >> p[i];
  }
  vector<int> line;
  rep(i,n * 4) {
    line.push_back(x - 2 * n + i);
  }

  int ans = 101;
  if(line.size() == 0) {
    cout << x << endl;
    return 0;
  }
  for(int a : line) {
    bool isContained = false;
    int dif = abs(x - abs(a));
    rep(i, n) {
      if(a == p[i]) isContained = true;
    }
    // cout << ans << " " << a << " " << dif << " " << isContained << endl;
    if(abs(x - ans) > dif && !isContained) {
      ans = a;
    }else if(abs(x - ans) == dif && !isContained) ans = min(ans,a);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int N;
  cin >> N;
  int count2 = 0;
  for(int i = 1;i <= N;i+=2){
  int count1 = 0;
  	for(int j = 1;j <= i;j+=2){
   	  if(i % j == 0){
        count1++;
      }
    }
    if(count1 == 8){
	  count2++;
    }
  }
  cout << count2;
}

Measured memory_bytes: 384
import java.util.*;
class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[][] a = new int[h+2][w+2];
        for(int i = 1; i<h+1; i++) {
            String s = sc.next();
            for(int j = 1; j<w+1; j++) {
                a[i][j] = (s.charAt(j-1) == '#')? 1: 0;
            }
        }

        for(int i = 1; i<h+1; i++) {
            for(int j = 1; j<w+1; j++) {
                if(a[i][j]==1 && a[i-1][j]
                        +a[i][j-1]+a[i][j]+a[i][j+1]
                        +a[i+1][j] <= 1) {
                    System.out.println("No");
                    return;
                }

            }
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 21972
from itertools import groupby, accumulate

# 入力
N, K = map(int, input().split())
S = input()

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[min(2 * K - 1, len(A) - 1)],
        A[-1] - A[max(-(2 * K), -len(A))],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)


Measured memory_bytes: 8804
#include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
	int weight;
	int n,v,w,c=0;
	int dp[1001][1001];
	while(scanf("%d\n",&weight) && weight){
		c++;
		rep(i,1001)rep(j,1001)dp[i][j]=0;
		
		scanf("%d\n",&n);
		for(int k=1;k<=n;k++){
			scanf("%d,%d\n",&v,&w);
			for(int i=0;i<=w;i++){
				dp[k][i] = dp[k-1][i];
			}
			for(int i=w;i<=weight;i++){
				dp[k][i] = max(dp[k-1][i],dp[k-1][i-w]+v);
			}
		}
		/*for(int k=0;k<=n;k++){
			for(int i=0;i<=weight;i++)
				printf("%4d",dp[k][i]);
			puts("");
		}*/
		printf("Case %d:\n",c);
		printf("%d\n",dp[n][weight]);
		for(int i=0;i<=weight;i++){
			if(dp[n][i]==dp[n][weight]){
				printf("%d\n",i);
				break;
			}
		}
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
using namespace std;


int main(){
	/*input*/
//	char s[11];
	string s;
	cin >> s;
	int size = s.length();
	/*calc*/
    int ans = 0;
    int tmp = 0;
    for(int i = 0; i < size; i++){
    	if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
    		tmp++;
    		if(i == size-1) ans=max(ans,tmp);
    	}
    	else{
    		ans = max(ans,tmp);
    		tmp = 0;
    	}
    }

    /*output*/
	cout<< ans <<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define SIZE 12
#define R(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define aah ios::sync_with_stdio(false)
char str[SIZE];
int main()
{
    aah;
    cin>>str;
    long long int ans=0;
    int w=strlen(str);
    for(int S=0;S<1<<(w-1);S++)
    {
         long long int now=0,sum=0;
         for(int i=0;i<w;i++)
         {
         	now*=10LL;
         	now+=str[i]-48;
         	if(i<w-1&&(S>>i&1))
         	{
         		sum+=now;
         		now=0;
            }
         }
         sum+=now;
         ans+=sum;
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 256
a, b, c, x, y = map(int, input().split())
sum = 0
if 2 * c < a + b:
  sum += min(x, y) * 2 * c
  if min(x, y) == x:
    if 2 * c < b:
      sum += (y - x) * 2 * c
    else:
      sum += (y - x) * b
  else:
    if 2 * c < a:
      sum += (x - y) * 2 * c
    else:
      sum += (x - y) * a
else:
  sum += x * a + y * b

print(sum)

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

template <typename T>
void print(const T &v);

int main()
{
    string T;
    cin >> T;
    for (char c : T)
    {
        if (c == 'D' || c == '?')
        {
            cout << 'D';
        }
        if (c == 'P')
        {
            cout << 'P';
        }
    }
    cout << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 3728
n, weight = map(int, input().split())
v = [0 for i in range(n)]
w = [0 for i in range(n)]

for i in range(n):
  v[i] , w[i] = map(int, input().split())

dp = [ [0 for i in range(weight + 1)] for i in range(n)]
for i in range(weight + 1):
  if(i >= w[0]):
    dp[0][i] = v[0]
for i in range(1, n):
  for j in range(weight + 1):
    if j - w[i] >= 0:
      dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
    else:
      dp[i][j] = dp[i - 1][j]
      
print(dp[n - 1][weight])


Measured memory_bytes: 41964
[i for i in [dict()] if not((i.update({'o': list(map(int, input().split()))}) or i.update({'w': i['o'][0]}) or i.update({'h': i['o'][1]}) or i.update({'x': i['o'][2] + i['o'][4]}) or i.update({'y': i['o'][3] + i['o'][4]}) or None) or (print('No') if (i['x']<=0 or i['w']<i['x']) or (i['y']<=0 or i['h']<i['y']) else print('Yes')) or None)]




Measured memory_bytes: 5608