akhauriyash/Code-Regression huggingface dataset:
import sys
_ = int(input())
ns = list(map(int, input().split()))
total = 1
flg = False
if 0 in ns:
    print(0)
    sys.exit(0)
for n in ns:
    if total > 10**18:
        flg = True
        break 
    total = total*n
if flg or total > 10**18:
    print(-1)
else:
    print(total)

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

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

ll ti[2000010];

int main() {

  ll n,t;cin>>n>>t;
  rep(i,0,n)cin>>ti[i];
  ll sum=0;
  rep(i,0,n-1){
    if(ti[i+1]-ti[i]<=t)sum+=ti[i+1]-ti[i];
    else sum+=t;
  }


  out(sum+t);


  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    
    int r, c;
    cin >> r >> c;
    
    int spreadSheet[101][101] = {0};
    
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> spreadSheet[i][j];
            spreadSheet[i][c] += spreadSheet[i][j];
            spreadSheet[r][j] += spreadSheet[i][j];
            spreadSheet[r][c] += spreadSheet[i][j];
        }
    }
    
    for(int i = 0; i <= r; i++){
        for(int j = 0; j <= c; j++){
            cout << spreadSheet[i][j] << ((j < c) ? " ":"\n");
        }
    }
    
    return 0;
}



Measured memory_bytes: 3132
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <inttypes.h>

int main(void){
	int a,b;

	scanf("%d %d",&a,&b);
	printf("%d",a*b);
	return 0;
}


Measured memory_bytes: 1736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
   int n,m;cin>>n>>m;
   cout<<n*(n-1)/2+m*(m-1)/2;
   
}

Measured memory_bytes: 256
A=int(input())
B=int(input())
C=int(input())
X=int(input())
ABC=0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if X==(500*a + 100*b + 50*c):
                ABC +=1
print(ABC)

Measured memory_bytes: 3064
CH = ["Z","a","b","c","d","e","f","g","h","i","j"]

def next_ch(n,s,index)
  if n == 1
    puts s
  else
    for i in 1..index+1
      next_ch(n-1,s+CH[i],[index,i].max)
    end
  end

end

n = gets.to_i
next_ch(n,"a",1)

Measured memory_bytes: 3068
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int W = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();

    int ans = 0;
    if (a+W < b) {
      ans = b - (a+W);
    } else if (b+W < a) {
      ans = a - (b+W);
    }
    
    System.out.println(ans);
  }
}

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

typedef long long int ll;
#define pb push_back
#define mp make_pair
#define N 200005

vector <int> adj[N];
int black[N],white[N],vis[N],vis1[N];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int n,i,u,v;
	cin>>n;
	for(i=1;i<n;i++){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	queue <pair<int,int>> p,q;
	p.push(mp(1,0));
	q.push(mp(n,0));
	while(!p.empty()){
		pair<int,int> s = p.front();
		vis[s.first]=1;
		black[s.first]=s.second;
		for(i=0;i<adj[s.first].size();i++)
			if(!vis[adj[s.first][i]])
				p.push(mp(adj[s.first][i],s.second+1));

		p.pop();

	}
	while(!q.empty()){
		pair<int,int> s = q.front();
		vis1[s.first]=1;
		white[s.first]=s.second;
		for(i=0;i<adj[s.first].size();i++)
			if(!vis1[adj[s.first][i]])
				q.push(mp(adj[s.first][i],s.second+1));

		q.pop();
	}
	int count=0;
	for(i=1;i<=n;i++){
		// cout<<black[i]<<" "<<white[i]<<endl;
		if(black[i]<=white[i]){
			count++;
		}
	}

	if(count>(n-count)){
		cout<<"Fennec"<<endl;
	}
	else
		cout<<"Snuke"<<endl;

	return 0;
}


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define intMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod = 1e9+7;

string s,t;
int n;
int main(){
    cin >> n;
	cin >> s >> t;
	string ans = "";
	for(int i = 0; i < n; i++){
		ans += s[i];
		ans += t[i];
	}
	cout << ans << endl;
}

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;

  int count;
  if(a==b&&a==c&&b==c){
    count=1;
  }
  else if(a!=b&&b!=c&&c!=a){
    count=3;
  }
  else{
    count=2;
  }
  
  cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int res = 0;
    for(int i = 0; i<=300;i++) {
        int h,w;
        cin >> h >> w;
        if (h == 0 && w == 0) {
            break;
        }
        for(int k = 0; k < h; k++) {
            for(int j = 0; j < w; j++) {
                if(j % 2 == 0) {
                    if( k % 2 == 0) {
                        cout << "#";
                    }else{
                        cout << ".";
                    }
                } else {
                    if( k % 2 == 0) {
                        cout << ".";
                    }else{
                        cout << "#";
                    }
                }                
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3004
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  
  int count = 0;
  bool flag = false;
  while (n--) {
    int a, b;
    cin >> a >> b;
    if (a == b) {
      count++;
    } else {
      count = 0;
    }
    if (count == 3) {
      flag = true;
    }
  }
  
  if (flag) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;

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

  int count = 0;
  for(int i=0;i<n-2;++i){
   if(s.substr(i, 3) == "ABC") count++;   
  }
  cout << count << endl;
}


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

using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define allpt(v) (v).begin(), (v).end()
#define allpt_c(v) (v).cbegin(), (v).cend()
#define allpt_r(v) (v).rbegin(), (v).rend()



const int mod = 1e9 + 7;
const string wsp = " ";
const string tb = "\t";
const string rt = "\n";

template <typename T>
void show1dvec(const vector<T> &v)
{
    if (v.size() == 0)
        return;
    int n = v.size() - 1;
    rep(i, n) cout << v[i] << wsp;
    cout << v[n] << rt;
    return;
}

template <typename T>
void show2dvec(const vector<vector<T>> &v)
{
    int n = v.size();
    rep(i, n) show1dvec(v[i]);
}

template <typename T, typename S>
bool myfind(T t, S s)
{
    return find(t.cbegin(), t.cend(), s) != t.cend();
}

vector<int> make_kmp_table(string t)
{
    int lt = t.length();
    VI kmptable(lt, 0);
    kmptable[0] = -1;

    return kmptable;
}

void djkstra(int s, VI &depth, VI &parent, const vector<VI> &connect, VI &indeg)
{
    vector<int> search = {s};
    vector<int> new_search;

    while (!search.empty())
    {
        for (auto i :search)
        {
            for (auto j : connect[i])
            {
                if (depth[j] < 1 + depth[i])
                {
                    indeg[j]--;
                    depth[j] = 1 + depth[i];
                    parent[j] = i + 1;
                    if (indeg[j] == 0)
                        new_search.push_back(j);
                }
            }
        }
        search.clear();
        search = new_search;
        new_search.clear();
    }
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    // int n;
    // string s, t;
    // cin >> n >> s;
    // VL dp(n + 1, 0ll);
    // vector<set<int>> callspell(n);
    // dp[0] = 1;
    // rep(i, n)
    // {
    //     cin >> t;
    // }

    // rep(i, n)
    // {
    //     for (int z : callspell[i])
    //     {
    //         dp[i + z - 1] += dp[i - 1];
    //         dp[i + z - 1] %= mod;
    //     }
    // }

    // cout << dp[n] << rt;

    int n, m, a, b, s;
    cin >> n >> m;
    VI parent(n, 0), depth(n, 0), indeg(n, 0);
    vector<VI> connect(n);
    rep(i, n + m - 1)
    {
        cin >> a >> b;
        a--, b--;
        connect[a].push_back(b);
        indeg[b]++;
    }
    rep(i, n) if (indeg[i] == 0) s = i;

    djkstra(s, depth, parent, connect, indeg);

    for (auto z : parent) cout << z << rt;

    return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
#include<cmath>
#include<string>
#include<iomanip>
#include <numeric>
#include <limits>
using namespace std;
 
int main()
{
string s; cin>>s;
int i = s.size() - 1;
while(true){
    if(i % 2 == 0){
        if(s.substr(0, i/2) == s.substr(i/2, i/2)){
            cout << i << endl;
            break;
         }
      }
      i--;
   }
return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(void){
    ll n;
    cin >> n;
    vector<ll> a;
    for(ll i = 0; i < n; i++){
        ll b; cin >> b;
        a.push_back(b);
    }
    ll ans = 1;
    for(ll i = 1; i < a.size()-1; i++){
        ll b = a[i]-a[i-1];
        ll c = a[i+1]-a[i];
        if(c==0){
            a.erase(a.begin()+i+1);
            i--; continue;
        }
        if(b*c<0) {
            ans++; i++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
typedef long long ll;
const int MAX = 999999999;

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

    if(d == 25) cout << "Christmas" << endl;
    else if(d == 24) cout << "Christmas Eve" << endl;
    else if(d == 23) cout << "Christmas Eve Eve" << endl;
    else if(d == 22) cout << "Christmas Eve Eve Eve" << endl;
}

Measured memory_bytes: 256
// Java program For handling Input/Output 
import java.io.*; 
import java.util.*;
import java.math.*;
//import java.awt.*;

public class Main 
{ 
    FastReader sc;
    //actual logic
    void solve() throws IOException{
        int h = sc.ni();
        int w = sc.ni();
        int n = sc.ni();

        System.out.println((int)Math.ceil(n/Math.max(w, h+0.0)));
    }

    //constructor
    Main()
    {
        try{  
            sc = new FastReader();
        }catch(Exception e){
            System.out.println(e);
        }
    }


    //main metohd
    public static void main(String[] args) throws IOException
    { 
     new Main().solve();
 }
    //Utility methods

 static class FastReader{
    BufferedReader br;
    StringTokenizer st;
    FastReader(){
        br = new BufferedReader(new InputStreamReader(System.in));
        try{
            st = new StringTokenizer(br.readLine());
        }catch(Exception e){
            System.out.println(e);
        }
    }

    FastReader(String s){
        try{
            br = new BufferedReader(new FileReader(s));
            st = new StringTokenizer(br.readLine());
        }catch(Exception e){
            System.out.println(e);
        }
    }

    String ns(){
        if(!st.hasMoreTokens())
        {
            try{
                st = new StringTokenizer(br.readLine());
            }catch(Exception e){
                System.out.println(e);
            }    
        }
        return st.nextToken();

    }

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

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

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


Measured memory_bytes: 23252
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;

LL n,k,q = 0,p[5005];
char ch = 'z';
string s,t;

int main(){
	cin >> n >> k;
	cin >> s;
	for(LL i = 0;i < n;i ++) ch = min(ch,s[i]);
	for(LL i = 0;i < n;i ++){
		p[i] = (s[i] == ch ? p[i - 1] + 1 : 0);
		q = max(q,p[i]);
	}
	q = max(q,p[n - 1] << 1);
	t = s; reverse(t.begin(),t.end()); s = s + t;
	t = s.substr(0,n);
	for(LL i = 1;i <= n;i ++) t = min(t,s.substr(i,n));
//	for(LL i = 0;i <= n;i ++) cout << s.substr(i,n) << endl;
//	cout << q << endl;
	for(LL i = 2;i <= k;i ++){
		s = t; reverse(s.begin(),s.end()); s += t;
		t = s.substr(n - q,n);
		q <<= 1; if(q > n) break;
	}
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
int N,A,B;
ll v[51],sum=0;
ll C[51][51];
void comb_table(int N){
  for(int i=0;i<=N;i++){
    for(int j=0;j<=i;j++){
      if(j==0 || j==i)C[i][j]=1ll;
      else C[i][j]=(C[i-1][j-1]+C[i-1][j]);
    }
  }
}
int main(){
  cin >> N >> A >> B;
  for(int i=0;i<N;i++) cin >> v[i];
  comb_table(N);
  sort(v,v+N,greater<ll>() );
  
  for(int i=0;i<A;i++)sum+=v[i];
  double ans=sum;
  ans/=A;
  printf("%f\n",ans);

  int num=0,pos=0;
  for(int i=0;i<N;i++){
    if(v[i]==v[A-1]){
      num++;
      if(i<A){
	pos++;
      }
    }
  }

  ll cnt=0;
  if(pos!=A){
    cnt=C[num][pos];
  }
  else{
    for(pos=A;pos<=B;pos++){
      cnt+=C[num][pos];
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

int n;
char str[105];

int main(){
    scanf("%s", str); n = strlen(str);
    int ans = 0;
    for(int i = 0, j = n - 1; i < j; i++, j--) ans += str[i] != str[j];
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct P{
  int t,c,x;
  bool f;
  P(){}
  P(int t,int c):t(t),c(c){x=f=0;}
  bool operator<(const P a)const{
    return t>a.t;
  } 
};
signed main(){
  int n;
  while(cin>>n,n){
    int t[n],c[n];
    for(int i=0;i<n;i++) cin>>t[i]>>c[i];
    priority_queue<P> q[2];
    for(int i=0;i<n;i++) q[0].push(P(t[i],c[i]*2-1));
    deque<P> v[2];
    while(!q[0].empty()){
      v[0].push_back(q[0].top());q[0].pop();
    }
    int ans=0;
    while(!v[0].empty()||!v[1].empty()){
      ans++;
      for(int k=0;k<2;k++){
	for(int i=0;i<(int)v[k].size();i++){
	  v[k][i].x++;
	  P p=v[k][i];
	  if((!i&&p.x>=p.t)||(i&&v[k][i-1].f&&p.x>=p.t)){
	    //cout<<ans<<":"<<k<<":"<<i<<" "<<p.t<<" "<<p.x<<" "<<p.c<<endl;
	    v[k][i].f=1;
	    if(p.c){
	      p.x=0;
	      p.c--;
	      q[!k].push(p);
	    }
	  }
	}
	while(!v[k].empty()&&v[k].front().f) v[k].pop_front();
      }
      for(int k=0;k<2;k++){
	while(!q[k].empty()){
	  v[k].push_back(q[k].top());q[k].pop();
	}
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3100
/*
    JAI JAGANNATH!
*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int lli;
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<lli,lli>
#define vi              vector<lli>
#define mii             map<lli,lli>
#define pqb             priority_queue<lli>
#define pqs             priority_queue<lli,vi,greater<lli> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            lli x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

void ss()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
void solve() {
	lli n;
	cin >> n;
	vector <lli> v1(n);
	vector <lli> v2(n);
	for (lli i = 0; i < n; i++) {
		cin >> v1[i] >> v2[i];
	}
	lli y, z;
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	if (n & 1) {
		y = v1[n / 2];
		z = v2[n / 2];
	} else {
		y = v1[n / 2] + v1[n / 2 - 1];
		z = v2[n / 2] + v2[n / 2 - 1];
	}
	cout << z - y + 1 << endl;
}
int main()
{
	ss();
	solve();
	return 0;
}



Measured memory_bytes: 6396
type ABC(stream:System.IO.TextReader) =
  member this.Scan1 f = stream.ReadLine() |> f
  member this.Scan2 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1]))
  member this.Scan3 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2]))
  member this.Scan4 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2], a.[3]))
  member this.ScanVecH f = stream.ReadLine().Split() |> Array.map f
  member this.ScanVecV n f = [| for i in 1..n -> stream.ReadLine() |> f |]
  member this.ScanMatrix n f  = [| for i in 1..n -> stream.ReadLine().Split() |> Array.map f |]
  member this.ScanCharMatrix n = [| for i in 1..n -> stream.ReadLine().ToCharArray() |]
  member this.Close () = stream.Close()

let util = ABC(stdin)

let s = util.Scan1 int

let ok3 = 
  [1..9]
  |> List.map (fun n -> 100*n+10*n+n)
let ok = ok3@[1111]

ok
|> List.find (fun n -> n >= s)
|> printfn "%d"

util.Close()


Measured memory_bytes: 14160
#include"bits/stdc++.h"
using namespace std;

vector<long long> a;
vector<pair<int, int>> ans;

void operation(int x, int y) {
    a[y] += a[x];
    ans.push_back({ x + 1, y + 1 });
}

int main() {
    int N;
    cin >> N;
    a.resize(N);
    long long max_index = 0, max_value = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (abs(a[i]) > max_value) {
            max_value = abs(a[i]);
            max_index = i;
        }
    }

    for (int i = 0; i < N; i++) {
        if (i == max_index) {
            continue;
        }
        operation(max_index, i);
    }

    if (a[0] >= 0) {
        for (int i = 0; i < N - 1; i++) {
            if (a[i] <= a[i + 1]) {
                continue;
            }
            operation(i, i + 1);
        }
    } else {
        for (int i = N - 1; i > 0; i--) {
            if (a[i - 1] <= a[i]) {
                continue;
            }
            operation(i, i - 1);
        }
    }

    cout << ans.size() << endl;
    for (auto p : ans) {
        cout << p.first << " " << p.second << endl;
    }
}

Measured memory_bytes: 256
use text_io::*;
use std::process::exit;
use im_rc::*;
use std::cmp::*;

fn main(){
    let mut n:usize = read!();
    let mut a:String = read!();
    let mut v:Vec<char> = a.chars().collect();
    if v.len()%2==1 {
        println!("No");
        exit(0);
    }
    for i in 0..v.len()/2 {
        if v[i]!=v[i+v.len()/2] {
            println!("No");
            exit(0);
        }
    }
    println!("Yes");
}

Measured memory_bytes: 2144
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std;
// dfmt on

void main()
{
    long A, B, C, K;
    scan(A, B, C, K);
    writeln(min(A, K) - min(C, max(0, K - A - B)));
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
const int mod = 1e9 + 7;

int n, k;

vector < pair <int, int> > all;
int suf[nax];
int pref[nax];

int mul (int a, int b) {
    return 1LL * a * b % mod;
}

int fix (int a) {
    return (a % mod + mod) % mod;
}

int main () {
    scanf("%d %d", &n, &k);

    for (int i = 0 ; i < n;  ++ i) {
        int x;
        scanf("%d", &x);

        all.emplace_back(abs(x), x >= 0 ? 1 : -1);
    }

    sort(all.rbegin(), all.rend());

    int p = 0;
    priority_queue <int, vector <int>, greater <int>> pos;
    priority_queue <int, vector <int>, greater <int>> neg;


    for (int i = 0 ; i < k ; ++ i) {
        p ^= (all[i].second == -1);
        if (all[i].second > 0) {
            pos.push(all[i].first);
        } else neg.push(all[i].first);
    }

    if (p == 0) {
        int ans = 1;
        for (int i = 0 ; i < k; ++ i) {
            int x = all[i].first;
            if (all[i].second == -1) x = fix(-x);
            ans = mul(ans, x);
        }
        return !printf("%d\n", ans);
    }

    auto get_product = [&]()-> int{
        int ans= 1;
        while (!pos.empty()) {
            ans = mul(ans, pos.top());
            pos.pop();
        }

        while (!neg.empty()) {
            ans = mul(ans, fix(-neg.top()));
            neg.pop();
        }

        return ans;
    };

    constexpr pair <int, int> invalid = make_pair(-1, -1);
    pair <int, int> ratio_pos = invalid;
    pair <int, int> ratio_neg = invalid;

    for (int i = k ; i < n ; ++ i) {
        if (all[i].second == 1) {
            if (ratio_pos == invalid) {
                ratio_pos = make_pair(all[i].first, neg.top());
            }
        } else if (all[i].second == -1) {
            if (pos.empty()) continue;
            if (ratio_neg == invalid) {
                ratio_neg = make_pair(all[i].first, pos.top());
            }
        }
    }

    bool go_pos = false;
    if (ratio_pos != invalid) {
        if (ratio_neg != invalid) {
            /**
            a / b c  / d
            */
            if (1LL * ratio_neg.first * ratio_pos.second <= 1LL * ratio_pos.first * ratio_neg.second)
                go_pos = true;
        } else go_pos = true;
    }

    if (!(ratio_pos == invalid &&ratio_neg == invalid)) {
            for (int i = k ; i < n ; ++ i) {
                if (all[i].second == 1 && go_pos) {
                    neg.pop();
                    pos.push(all[i].first);
                    return !printf("%d\n", get_product());
                } else if (all[i].second == -1 && !go_pos) {
                    if (pos.empty()) continue;
                    pos.pop();
                    neg.push(all[i].first);
                    return !printf("%d\n", get_product());
                }
            }
            assert(false);
    }

    /// cannot make positive

    reverse(all.begin(), all.end());

    int ans = 1;

    for (int i = 0 ; i < k; ++ i) {
        ans = mul(ans, all[i].first);
    }
    printf("%d\n", fix(-ans));


}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 6568
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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

vector<int> parent(maxn); //Initialise parent[i]=i;
vector<int> sze(maxn, 1);

int find_parent(int v) {
	if (v == parent[v]) return v;
	return parent[v] = find_parent(parent[v]);
}

void union_set(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);

	if (a != b) {
		if (sze[a] < sze[b]) swap(a, b);

		parent[b] = a;
		sze[a] += sze[b];
	}
	return;
}

/*
1 	2 	3
A1 	A2 	A3

*/

int main() {

	int n, m; cin >> n >> m;
	for (int i = 0; i <= n; i++) parent[i] = i;

	for (int i = 1; i <= m; i++) {
		int x, y, z; cin >> x >> y >> z;
		/*if (z % 2 == 0) */union_set(x, y);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) if (find_parent(i) == i) ans++;
	cout << ans;


	return 0;
}

Measured memory_bytes: 18208
N = int(input())
D, X = map(int, input().split())
A = [int(input()) for i in range(N)]
ans = 0
for i in range(N):
    if(D % A[i]):
        ans += D // A[i] + 1
    else:
        ans += D // A[i]
print(ans + X)

Measured memory_bytes: 3060
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int main(){
	int N;
	cin >> N;
	string S;
	cin >> S;
	for(int i = 0; i < S.size(); i++){
		if(S[i] + N > 'Z'){
			S[i] = S[i] + N - 26;
		}else{
			S[i] = S[i] + N;
		}
	}
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B, C; cin >> A >> B >> C;
  for(int i = 1; i <= B; i++){
    if(A*i%B == C){
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():

    S = input()

    n = len(S)
    a = "10" * (n // 2) + "1" * (n % 2)
    b = "01" * (n // 2) + "0" * (n % 2)

    result = min(bin(int(S, 2) ^ int(a, 2)).count("1"),
                 bin(int(S, 2) ^ int(b, 2)).count("1"))

    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3444
H = int(input())
a = list(map(int, input().split()))
def maxHeapify(A, i):
    l = 2*i + 1
    r = 2*i + 2
    largest = i
    if l<H and A[largest] < A[l]:
        largest = l 
    if r<H and A[largest] < A[r]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)

def buildHeap(A):
    for i in range(H//2, -1,-1):
        maxHeapify(A, i)

buildHeap(a)

print(' '+' '.join(list(map(str, a))))



Measured memory_bytes: 63736
N, M = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

mod = 10 ** 9 + 7


def solve(x, y):
    dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] += dp[i - 1][j - 1] + 1
                dp[i][j] %= mod
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod

    return dp


ans = solve(s_list, t_list)
print((ans[N][M] + 1) % mod)


Measured memory_bytes: 74588
/*---------------------------------

 @Author:   Dicer
 @DateTime: 2019-01-11 19:41:55

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

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define clr(s, x) memset(s, x, sizeof(s))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"
inline int read(){int r=0;char c=getchar();while(c<'0'||c>'9') {c=getchar();}while(c>='0'&&c<='9') {r=r*10+c-'0';c=getchar();}return r;}
inline ll readll(){ll r=0;char c=getchar();while(c<'0'||c>'9') {c=getchar();}while(c>='0'&&c<='9') {r=r*10+c-'0';c=getchar();}return r;}
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
inline ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const double eps = 1e-8;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int MAXN = 1e5+7;
const int MAXM = 1e5+7;

int a[MAXN], b[MAXN], c[MAXN], dp[MAXN][4];
int main(int argc, char const *argv[])
{
	int n;
	cin >> n;
	for(int i=1;i<=n;++i)	cin >> a[i] >> b[i] >> c[i];
	for(int i=1;i<=n;++i){
		dp[i][1] = a[i]+max(dp[i-1][2], dp[i-1][3]);
		dp[i][2] = b[i]+max(dp[i-1][1], dp[i-1][3]);
		dp[i][3] = c[i]+max(dp[i-1][1], dp[i-1][2]);
	}
	printf("%d\n", max(dp[n][1], max(dp[n][2], dp[n][3])));
	return 0;
}

Measured memory_bytes: 2944
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int64_t dceil(int64_t, int64_t);
int64_t dfloor(int64_t, int64_t);

int64_t dceil(int64_t x, int64_t y) {
  if (y < 0) {
    return dceil(-x, -y);
  }
  if (x < 0) {
    return -dfloor(-x, y);
  }
  return (x + y - 1) / y;
}

int64_t dfloor(int64_t x, int64_t y) {
  if (y < 0) {
    return dfloor(-x, -y);
  }
  if (x < 0) {
    return -dceil(-x, y);
  }
  return x / y;
}

int main() {
  int64_t k, q;
  cin >> k >> q;

  vector<int64_t> d(k);
  rep(i, k) { cin >> d[i]; }

  rep(i, q) {
    int64_t n, x, m;
    cin >> n >> x >> m;

    vector<int64_t> drem(k + 1), cnt(k + 1);
    drem[0] = 0;
    cnt[0] = 0;
    rep(j, k) {
      drem[j + 1] = d[j] % m;
      cnt[j + 1] = (drem[j + 1] == 0 ? 1 : 0);

      drem[j + 1] += drem[j];
      cnt[j + 1] += cnt[j];
    }

    int64_t eqcnt = ((n - 1) / k) * cnt[k] + cnt[(n - 1) % k];

    int64_t y = x + ((n - 1) / k) * drem[k] + drem[(n - 1) % k];
    int64_t s = dfloor(x, m) + 1;
    int64_t t = dfloor(y, m);
    int64_t gtcnt = t - s + 1;

    int64_t result = (n - 1) - eqcnt - gtcnt;
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 384
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| min!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| max!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}


macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    use std::collections::HashMap;
    let mut memo = HashMap::new();
    for _ in 0..n {
        let mut cs: Vec<char> = sc.cin::<String>().chars().collect();
        cs.sort();
        let counter = memo.entry(cs).or_insert(0u64);
        *counter += 1;
    }
    let mut ans: u64 = 0;
    for (_, count) in memo.iter() {
        ans += count * (count - 1) / 2;
    }
    put!(ans);
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


Measured memory_bytes: 16636
#include <iostream>

using namespace std;

int N;
int c[100001];

int main(){
    int n;
    long long count = 0;
    cin >> N;
    for(int i=0;i<100001;i++) c[i] = 0;
    for(int i=0;i<N;i++){
        cin >> n;
        if(n <= 100000) c[n]++;
        else count++;
    }
    for(int i=0;i<100001;i++){
        if(c[i] == i) continue;
        if(c[i] < i) count += c[i];
        else count += c[i] - i;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
char s[N];
int n,m,Q,a[N][N],b[N][N],s1[N][N],s2[N][N],s3[N][N],s4[N][N];
int main(){
	scanf( "%d%d%d", &n, &m, &Q );
	for( int i = 1; i <= n; i++ ){
		scanf( "%s", s+1 );
		for( int j = 1; j <= m; j++ ) a[i][j] = s[j] - '0';
	} 
	for( int i = 1; i <= n; i++ )
		for( int j = 1; j <= m; j++ ){
			s3[i][j] = s3[i][j-1]; s4[i][j] = s4[i-1][j];
			if( a[i][j] ){
				if( a[i][j+1] ) b[i][j]++, s3[i][j]++;
				if( a[i+1][j] ) b[i][j]++, s4[i][j]++;
			}
		}
	for( int i = 1; i <= n; i++ )
		for( int j = 1; j <= m; j++ )
			s1[i][j] = a[i][j] + s1[i][j-1] + s1[i-1][j] - s1[i-1][j-1],
			s2[i][j] = b[i][j] + s2[i][j-1] + s2[i-1][j] - s2[i-1][j-1];
	while( Q-- ){
		int c, d, e, f;
		scanf( "%d%d%d%d", &c, &d, &e, &f );
		printf( "%d\n", s1[e][f] - s1[c-1][f] - s1[e][d-1] + s1[c-1][d-1] - 
		( s2[e-1][f-1] - s2[c-1][f-1] - s2[e-1][d-1] + s2[c-1][d-1] + s4[e-1][f] - s4[c-1][f] + s3[e][f-1] - s3[e][d-1] ) );
	}
	return 0;
}

Measured memory_bytes: 95872
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=998244353,maxn=32768;
int n,m,e,i,j,fac[maxn+5],inv[maxn+5],fi[maxn+5],w[maxn+5],rev[maxn+5];
int a[maxn+5],b[maxn+5];
string s,t;
int qp(int x,int y)
{
	int z=1;
	while(y)
	{
		if(y&1){
			z=1ll*z*x%mod;
		}
		y/=2;
		x=1ll*x*x%mod;
	}
	return z;
}
void init()
{
	int i;
	w[0]=inv[1]=fac[0]=fac[1]=fi[0]=fi[1]=1;w[1]=qp(3,(mod-1)/maxn);
	fz(i,2,maxn){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fi[i]=1ll*fi[i-1]*inv[i]%mod;
		w[i]=1ll*w[i-1]*w[1]%mod;
	}
}
int getrev(int x)
{
	int len=1,i;
	while(len<=x){
		len*=2;
	}
	fz0k(i,len){
		rev[i]=rev[i/2]/2+((i&1)*(len/2));
	}
	return len;
}
void ntt(int *a,int len,int op)
{
	int i,j,k;
	fz0k(i,len) if(i<rev[i])swap(a[i],a[rev[i]]);
	for(i=1;i<len;i<<=1){
		int ys=maxn/i/2;
		for(j=0;j<len;j+=i+i){
			int t=(op==1?0:maxn);
			fz0k(k,i){
				int x=a[j+k],y=1ll*a[j+k+i]*w[t]%mod;
				a[j+k]=(x+y)%mod;
				a[j+k+i]=(x-y+mod)%mod; 
				t+=op*ys;
			}
		}
	}
	if(op==-1) fz0k(i,len) a[i]=1ll*a[i]*inv[len]%mod;
}
int main()
{
	init();
	cin>>s>>t;
	n=s.length();
	s=" "+s;t=" "+t;
	fz1(i,n){
		if((s[i]&15)&&(t[i]&15)){
			m++;
		}
		else if((s[i]&15)){
			e++;
		}
	}
	int len=getrev(m*2+1); 
	fz0g(i,m){
		a[i]=fi[i+1];
	}
	b[0]=1;
	int y=e;
	while(y)
	{
		ntt(a,len,1);
//		ntt(a,len,-1);
		if(y&1){
			ntt(b,len,1);
			fz0k(i,len) b[i]=1ll*a[i]*b[i]%mod;
			ntt(b,len,-1);
			fz(i,m+1,len) b[i]=0;
		}
		fz0k(i,len) a[i]=1ll*a[i]*a[i]%mod;
		ntt(a,len,-1);
		fz(i,m+1,len) a[i]=0;
		y/=2;
	}
	int ans=0;
	fz0g(i,m){
		inc(ans,b[i])
	}
	printf("%d\n",1ll*ans*fac[e]%mod*fac[m]%mod*fac[e+m]%mod);
	return 0;
}

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

int main() {
	int n; cin >> n;
	vector<int> a(n);
	int mx = 0;
	int sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
		mx = max(mx, a[i]);
	}
	if (mx < sum-mx) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long solve(vector<long long> neg, vector<long long> pos, int k)
{
	long long ans = 1;
	int j = 0;
	if(k&1)
	{
		if(pos.size()>0)
			ans *= pos.front(),--k,++j;
		else return -1;
	}
	vector<long long> v;
	for(int i=j;i+1<pos.size();i+=2)	
		v.push_back(pos[i]*pos[i+1]);
	for(int i=0;i+1<neg.size();i+=2)	
		v.push_back(neg[i]*neg[i+1]);
	if(v.size()<k/2)
		return -1;
	sort(v.rbegin(),v.rend());
	for(int i=0;i<k/2;++i)
		ans *= v[i]%MOD, ans %= MOD;
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	long long x;
	vector<long long> neg,pos,zero;
	while(n--)
	{
		cin>>x;
		if(x<0)
			neg.push_back(abs(x));
		else if(x>0)
			pos.push_back(x);
		else
			zero.push_back(x);
	}
	sort(pos.rbegin(),pos.rend());
	sort(neg.rbegin(),neg.rend());
	long long ans = solve(neg,pos,k);
	if(ans<0)
	{
		if(zero.size()>0)
			cout<<"0"<<endl;
		else
		{
			for(long long y:neg)
				pos.push_back(y);	
			sort(pos.begin(),pos.end());
			ans = 1;
			while(k--)			
				ans *= pos[k], ans %= MOD;
			cout<<MOD-ans<<endl;
		}
	}
	else cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8104
//q20.cpp
//Tue Aug 11 21:40:09 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

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

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

	vector<ll> a(n);
	rep(i,n) cin >> a[i];

	vector<ll> b(n);
	rep(i,n) cin >> b[i];

	vector<ll> c(n);
	rep(i,n) cin >> c[i];

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

	ll ans = 0;
	rep(i,n){
		ll mid = b[i];
		auto itrtop = upper_bound(c.begin(),c.end(),mid);
		ll top = c.end()-itrtop;
		auto itrbot = lower_bound(a.begin(),a.end(),mid);
		ll bottom;
		if (*itrbot == mid){
			if (itrbot==a.begin()){
				bottom = 0;
			}else {
				bottom = itrbot-a.begin();
			}
		}else {
			bottom = itrbot-a.begin();
		}
//		cout << top << " " << bottom << endl;
		ans += top*bottom;
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 5644
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll max(ll a,ll b)
{
    if(a>b)
    {
        return a;
    }
    else
    {
        return b;
    }
    
    
}
int main()
{
    
    ll n;cin>>n;
    ll a[n+1]={0};
    ll b[n+1]={0};
    ll c[n+1]={0};
    ll dp1[n+1]={0};
    ll dp2[n+1]={0};
    ll dp3[n+1]={0};
ll i=1;
while(i<=n)
{
    cin>>a[i]>>b[i]>>c[i];
    i++;
}
    i=1;
    while(i<=n)
    {
        if(i==1)
        {
            dp1[i]= a[i] ;
            dp2[i]= b[i] ;
            dp3[i]= c[i] ;
        }
        else
        {
            dp1[i]= a[i] + max(dp2[i-1],dp3[i-1])  ;
            
            dp2[i]= b[i] + max(dp1[i-1],dp3[i-1])  ;
            
            dp3[i]= c[i] + max(dp2[i-1],dp1[i-1])  ;
           
        }
        
        
        i++;
    }
    
    ll opo = max(dp3[n],max(dp1[n],dp2[n]));
    
    
    
    cout<<opo;
    
    
    
    
    
    return 0;
}



Measured memory_bytes: 4992
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// nがあり、nの数だけの整数の入力
			long n = sc.nextLong();
			Set<String> sn = new HashSet<>();
			for (long i = 0; i < n; i++) {
				sn.add(sc.next());
			}
			System.out.println(sn.size());
		}
	}

	/**
	 * 最小公倍数
	 */
	static long lcm(long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return c / b;
	}

	/**
	 * 最大公約数
	 */
	static long gcd(long a, long b) {
		long temp;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return b;
	}
}

Measured memory_bytes: 77184
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

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

int main(){
	int n;
	while(cin>>n,n){
		map<int,int> data;
		data.clear();
		for(int i =0;i <n;i++){
			int x;
			cin>>x;
			data[x]++;
		}
		for(int i =0;i <=9;i++){
			if(data[i]==0)cout <<"-"<<endl;
			else{
				for(int j =0;j <data[i];j++){
					cout <<"*";
				}
				cout <<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1188
n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])

Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	edges := make(map[int]map[int]int)
	for i := 0; i < n; i++ {
		edges[i] = make(map[int]int)
	}

	for i := 0; i < n-1; i++ {
		var u, v, w int
		fmt.Scan(&u, &v, &w)
		u--
		v--
		edges[u][v] = w
		edges[v][u] = w
	}

	costs := calc(n, edges)
	for i := 0; i < n; i++ {
		fmt.Println(costs[i] % 2)
	}
}

func calc(n int, edges map[int]map[int]int) []int {
	costs := make([]int, n)

	var dfs func(i, p int)
	dfs = func(v, p int) {
		e := edges[v]
		for u, w := range e {
			if u == p {
				continue
			}
			costs[u] = costs[v] + w
			dfs(u, v)
		}
	}
	dfs(0, -1)

	return costs
}


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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

    lint n, a, b, c, x;
    while(cin >> n >> a >> b >> c >> x, n){
        vector<lint> y(n);
        rep(i, n){
            cin >> y[i];
        }
        lint ans = -1;
        int j = 0;
        rep(i, 10001){
            if(x == y[j]){
                ++j;
            }
            if(j == n){
                ans = i;
                break;
            }
            x = (a * x + b) % c;
        }

        cout << ans << endl;
    }

    return 0;
}


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

#define int int64_t

signed main()
{
    int n, a[80], money, kabu, ans;
    
    cin >> n;
    for(int i=0 ;i<n; i++ ){
        cin >> a[i];
    }
    
    ans = 1000;
    for(int i=1 ;i<n ;i++ ){
        money = 1000, kabu = 0;
        for(int j=0 ;j<i ;j++ ){
            if(a[j] < a[j+1]){
                kabu += money / a[j];
                money = money % a[j];
            } else if(a[j] > a[j+1]) {
                money += a[j] * kabu;
                kabu = 0;
            }
        }
        ans = max(money + kabu * a[i], ans);
    }
    
    cout << ans << endl;
    
    return (0);
}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
static const int N = 100;

int main(int argc, char const *argv[])
{
    int M[N][N];
    int n, u, k, v;

    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            M[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; j++) {
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j) cout << " ";
            cout << M[i][j];
        }
        cout << endl;
    }
    return 0;
}




Measured memory_bytes: 3112
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define LL long long
#define MOD 1000000007
ll N, M, K, ans, mi, A;
string s;
int main() {
	cin >> N>>M;
	vector<string>v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	sort(v.begin(), v.end());
	for (int i = 0; i < N; i++) {
		cout << v[i];
	}
	cout << endl;
	return 0;

}



Measured memory_bytes: 256