akhauriyash/Code-Regression huggingface dataset:
n,m= list(map(int, input().split()))
h= list(map(int, input().split()))
sub=set()
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]>h[b-1]:
        sub.add(b)
    elif h[a-1]<h[b-1]:
        sub.add(a)
    else:
        sub.add(a)
        sub.add(b)
print(n-len(sub))

Measured memory_bytes: 20096
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
from bisect import insort
sys.setrecursionlimit(10**9)

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

    ch_max = 0
    for a in A:
        if ch_max + 1 == a:
            ch_max += 1

    if ch_max == 0:
        print(-1)
        exit()

    print(N - ch_max)




if __name__ == "__main__":
  main()


Measured memory_bytes: 36104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		int[] h = new int[n];
		
		for(int i=0; i<n; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			h[i] = sc.nextInt();
		}
		
		
		for(int i=0; i<=100; i++) {
			for(int j=0; j<=100; j++) {
				int H = 0;
				boolean flag = true;
				for(int p=0; p<n; p++) {
					if(h[p]!=0) {
						H = h[p] + Math.abs(i-x[p]) + Math.abs(j-y[p]);
					}
				}
				for(int k=0; k<n; k++) {
					if(h[k] != Math.max(H - Math.abs(i-x[k]) - Math.abs(j-y[k]), 0)) {
						flag = false;
					}
				}
				if(flag) {
					System.out.println(i + " " + j + " " + H);
				}
			}
		}
		
	}
}


Measured memory_bytes: 24264
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
  ios::sync_with_stdio(false);
  int a,b;
  cin>>a>>b;
  if(a*500>=b)cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}


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

r0 = int(input())
r1 = int(input())
max = r1-r0
min = min(r0,r1)
for i in range(n-2):
    r = int(input())
    if max < r-min:
        max = r-min
    if min > r:
        min = r
print(max)

Measured memory_bytes: 7652
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int N;
	cin >> N;
	int MAX = 0;
	int sum = 0;
	for(int i=0; i<N; ++i){
		int p;
		cin >> p;
		sum += p;
		MAX = max(MAX, p);
	}
	cout << sum - MAX/2 << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
 
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int inf = 1e9;
const int mod = 1e9 + 7;
 
int dfs(const vector<string> &s, int i, int j) {
    if (isdigit(s[i][j])) {
        return s[i][j] - '0';
    }
 
    int ret = (s[i][j] == '+' ? 0 : 1);
    int nj = j + 1;
    rep2(ni, i + 1, s.size()) {
        if (nj >= s[ni].size()) break;
        if (s[ni][nj] == '.') continue;
        if (s[i][j] == '+') ret += dfs(s, ni, nj);
        if (s[i][j] == '*') ret *= dfs(s, ni, nj);
    }
    return ret;
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int n;
    while (cin >> n, n) {
        vector<string> s(n);
        rep(i, n) cin >> s[i];
        cout << dfs(s, 0, 0) << endl;
    }
}

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

int main(){
    long long rahul;
    cin>>rahul;
    long long flag=0;
    
    while(rahul!=0){
        long long x=rahul%10;
        rahul=rahul/10;
        if(x==7){
            flag=1;
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(flag==0){
        cout<<"No"<<"\n";
    }
}

Measured memory_bytes: 3588
#include <cstdio>
#include <cstdlib>
using namespace std;

int main() {
    int x, a, b;
    scanf("%d %d %d", &x, &a, &b);
    if(b <= a) {
        printf("delicious\n");
    }else if(b > a && b-a <= x) {
        printf("safe\n");
    }else{
        printf("dangerous\n");
    }
    // system("pause");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll  long long
#define ull unsigned long long  
using namespace std;
#define  inf 1e18+18
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
#define  f1(i,n) for(i=1;i<=n;i++)
#define f0(i,n)  for(i=0;i<n;i++)
#define w(x)   while(x--)
const int maxn=1000001;
#define  pq priority_queue
#define  ff first
#define  ss second 
#define pb  push_back
#define lb lower_bound
int main()
{
   
   ll i,j,k,l,m,n;
   cin>>n;
   ll a[n],b[n];
   for(i=0;i<n;i++)
   	cin>>a[i];
   for(i=0;i<n;i++)
   	cin>>b[i];
   map<ll,ll>mp;
   ll dp[n];
   ll ans=b[0];
   dp[0]=b[0];
   mp[a[0]]=dp[0];
   for(i=1;i<n;i++)
   {
    dp[i]=b[i];
    auto it=mp.lb(a[i]);
    if(it!=mp.begin())
    {
    	it--;
    	dp[i]+=it->second;
    }
    mp[a[i]]=dp[i];
    auto itr=mp.upper_bound(a[i]);
    while(itr!=mp.end()&&itr->ss<=dp[i])
    {
    	auto temp=itr;
    	temp++;
    	mp.erase(itr);
    	itr=temp;
    }
    ans=max(ans,dp[i]);

   }
   cout<<ans;

   
}

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

using namespace std;

#define all(x) (x).begin(), (x).end()

typedef unsigned long long ull;

const int N = 1e5 + 10;
int p[N];
int ansl, ansr;

bool check(string s, char c) {
  int n = s.size();
  for (int i = 1; i <= n; i++) {
    p[i] = (s[i - 1] == c);
    p[i] += p[i - 1];
  }
  int mn = 1e9, pos = 1;
  for (int i = 1; i <= n; i++) {
    int mykey = 2 * p[i] - i - 1;
    if (mn < mykey) {
      ansl = pos, ansr = i; return true;
    }
    mykey = 2 * p[i - 1] - i;
    if (mn > mykey) {
      mn = mykey; pos = i;
    }
  }
  return false;
}

void solve() {
  string s; cin >> s;
  for (char c = 'a'; c <= 'z'; c++) {
    if (check(s, c)) {
      cout << ansl << " " << ansr; return;
    }
  }
  cout << -1 << " " << -1;
}

// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES (n == 1)

int main() {
  ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  //cout << 1.0 * clock() / CLOCKS_PER_SEC << endl;
  solve();
}


Measured memory_bytes: 4144
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    D, T, S = MI()
    a = D / S
    if a <= T:
        print('Yes')
    else:
        print('No')









if __name__ == "__main__":
    main()




Measured memory_bytes: 74476
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    vl a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
    }

    ll ans = 0;
    ll cnt = 0;
    for(ll i = n-1; i >= 0; i--) {
        a[i] += cnt;
        if(a[i]%b[i] != 0) {
            ans += b[i] - a[i]%b[i];
            cnt += b[i] - a[i]%b[i];
        }
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

    for (int i=0;i<str.size()-1;i++)
    {
        if (str[i] == str[i+1])
        {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp
b = gets.chomp
c = gets.chomp

ans = 0

(0...n).each do |i|
    if a[i] != b[i]
        ans += 1
        if a[i] != c[i] and b[i] != c[i]
            ans += 1
        end
    elsif b[i] != c[i]
        ans += 1
    elsif a[i] != c[i]
        ans += 1
    end
end

puts ans

Measured memory_bytes: 1788
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    
    String str = scanner.next();
    String answer = "No";
    if(str.charAt(2) == str.charAt(3)){
      if(str.charAt(4) == str.charAt(5)){
        answer = "Yes";
      }
    }
    System.out.println(answer);
  }
}

Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    ll N, A, B, ans=0;
    in3(N, A, B);
    rep(i,N){
        ll x = i+1, sum=0;
        while(x){
            sum += x%10;
            x /= 10;
        }
        if(A<=sum && sum<=B) ans += i+1;
    }
    put(ans);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main() {
	int n, x;
	cin >> n >> x;
	vector<int>v(n+1,0);
	repp(i, 1, n+1)cin >> v[i];
	int sum = 0; int i = 0;
	for (i = 1; i <= n; ++i) {
		sum += v[i];
		if (sum > x)break;
		
	}
	cout << i << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>
#include <chrono>


#define rep(i,p,q) for(ll i = p;i < q;i++)
#define ll long long

using namespace std;

vector<vector<ll>> graph;
vector<ll> query;
vector<ll> ans;
vector<ll> visited;


const long long MAX_N = 1 << 17;

long long dat[2 * MAX_N - 1];

//141 E
int main(void) {
	ll n;
	string s;
	cin >> n >> s;
	ll ub = n/2+1, lb = 0;
	while (ub - lb > 1) {
		ll len = (ub + lb) / 2;
		rep(i, 0, n - len) {
			string subStr = s.substr(i, len);
			if (subStr == "")break;
			auto pos = s.find(subStr, i + len);
			if (pos != string::npos) {
				lb = len;
				break;
			}
		}
		if (lb != len) ub = len;
	}
	cout << lb << endl;
}

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

int main(){
  int n,p,q;
  cin>>n>>p>>q;
  string s;
  cin>>s;
  int c=0,t=0;
  for(int i=0;i<n;i++)
  {
    if(s[i]=='a'&&c< p+q)
    {
      c++;
      cout<<"Yes"<<endl;   
    }
    else if(s[i]=='b'&&c<(p+q)&&t<q)
     {
      t++;
      c++;
      cout<<"Yes"<<endl;  
    }
    else if(s[i]=='c'){
      cout<<"No"<<endl;
    }
    else{
      cout<<"No"<<endl;
    }
 }
    return 0;  
}

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

int main(){
	int n;
	scanf("%d", &n);
	int a = n / 1.08;
	if(fabs(a * 1.08 - n) <= 0.0000001)printf("%d\n", a);
	else if((a + 1) * 1.08 > n && (a + 1) * 1.08 < n + 1)printf("%d\n", a + 1);
	//else if((a + 2) * 1.08 > n && (a + 2) * 1.08 < n + 1)printf("%d\n", a + 2);
	else printf(":(\n");
}


Measured memory_bytes: 256
#include <iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
#define mod 1000000007
#define ll long long
#define pr pair<int,int>
#define all vec.begin(),vec.end()
#define REP(i,a,b) for (int i = a; i < b; i++)
#define fi first
#define se second
#define pushb push_back
#define makep make_pair

using namespace std;

int main(){
	int n,t;
	cin >> n >> t;
	int arr[n];
	int k=0;
	while(cin >> arr[k++])
		;
	int sum =0;
	REP(i,1,n){
		if(arr[i] - arr[i-1] > t)
			sum += t;
		else
			sum += arr[i] - arr[i-1];
	}
	cout << sum + t;
	return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

long long N, A[1 << 18];
long long Q, B[1 << 18], C[1 << 18];
long long cnt[1 << 18], S;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) cnt[A[i]]++;
	for (int i = 1; i <= N; i++) S += A[i];
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> B[i] >> C[i];
		S += 1LL * (C[i] - B[i]) * cnt[B[i]];
		cnt[C[i]] += cnt[B[i]];
		cnt[B[i]] = 0;
		cout << S << endl;
	}
	return 0;
}

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

using namespace std;

int main(){

	int n, p;
	int count=1;
	int flag=0;
	vector<int> a;

	cin>> n;
	a.resize(n+1);
	a[0]=1;

	for(int i=1;i<n+1;i++) cin>> a[i];

	p=0;
	for(int i=0;i<100002;i++){
		//cout<< p << " " << a[p] << endl;
		p=a[p];
		if(i==100001){
			count=-1;
			flag=1;
		}else if(a[p]==2) flag=1;
		if(flag==1) break;
		count++;
		//a[p]=-1;
	}

	cout<< count << endl;

}

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

int main(void){
  int A,B,C,D,men1,men2;
  cin>>A>>B>>C>>D;
  men1=A*B;
  men2=C*D;
  if(men1<=men2){
    cout<<men2;
  }
  else{
    cout<<men1;
  }
  return 0;
  


}






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

using namespace std;

int main(){
    int H, W;
    cin >> H >> W;
    char s[H][W];
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin >> s[i][j];
        }
    }
    bool ans = true;

    pair<int, int> dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(s[i][j] == '#'){
                bool temp = false;
                for (auto d : dir){
                    if(0 <= i + d.first && i + d.first < H && 0 <= j + d.second && j + d.second < W){
                        if(s[i + d.first][j + d.second] == '#') temp = true;
                    }
                }
                ans = ans && temp;
            }
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int32_t main(){
std::ios::sync_with_stdio(false);
int n;cin>>n;
int h[n];
int dp[n];
for(int i=0;i<n;i++)
{
cin>>h[i];
}
int x=(h[0]-h[1]);
dp[0]=0;
dp[1]=abs(x);
for(int i=2;i<n;i++){
    int x=(h[i-1]-h[i]);
    int y=(h[i-2]-h[i]);
    dp[i]=min((dp[i-1]+abs(x)),dp[i-2]+abs(y));
}
cout<<dp[n-1];

return 0;
}


Measured memory_bytes: 1792
#pragma region Include
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma endregion

using namespace std;

#pragma region Macros
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define all(c) (c).begin(), (c).end()
#define dump(x) \
  cout << "Line " << __LINE__ << " : " << #x << " = " << (x) << endl
template <class T>
using VV = vector<vector<T>>;

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  os << "[";
  rep(i, vec.size()) os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  os << "]";
  return os;
}

template <typename T>
ostream& operator<<(ostream& os, vector<vector<T>>& mat) {
  os << "[";
  rep(i, mat.size()) os << mat[i] << (i + 1 == mat.size() ? "" : ",\n ");
  os << "]";
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x;
  return is;
}

template <typename V, typename H>
void resize(vector<V>& vec, const H head) {
  vec.resize(head);
}

template <typename V, typename H, typename... T>
void resize(vector<V>& vec, const H& head, const T... tail) {
  vec.resize(head);
  for (auto& v : vec) resize(v, tail...);
}
constexpr double EPS = 1e-10;
const int INF = 0x3f3f3f3f;
#pragma endregion

int main() {
  string S;
  ll K;
  cin >> S;
  cin >> K;
  ll ans;

  int n = S.length();
  int pre = 1;
  for (int i = 1; i < n; ++i) {
    if (S[i] != S[i - 1])
      break;
    else
      ++pre;
  }
  if (pre == n) {
    ans = n * K / 2;
    cout << ans << endl;
    return 0;
  }

  int suf = 1;
  for (int i = n - 2; i >= 0; --i) {
    if (S[i] != S[i + 1])
      break;
    else
      ++suf;
  }

  int mid = 0;
  int cont = 1;
  for (int i = pre + 1; i < n - suf; ++i) {
    if (S[i] == S[i - 1]) {
      ++cont;
    } else {
      mid += cont / 2;
      cont = 1;
    }
  }
  mid += cont / 2;

  if (S[0] != S[n - 1]) {
    ans = (pre / 2 + mid + suf / 2) * K;
  } else {
    ans = pre / 2 + mid * K + (pre + suf) / 2 * (K - 1) + suf / 2;
  }
  // dump(pre);
  // dump(mid);
  // dump(suf);
  cout << ans << endl;

  return 0;
}

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

int main(void){
	int X, N;
	cin >> X >> N;
	int p[N];
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}

	for (int i = 0; i < 100; i++) {
		int l = X - i;
		int r = X + i;
		int fl = 1;
		int fr = 1;
		for (int j = 0; j < N; j++) {
			if (p[j] != l){
				fl *= 1;
			} 
			else fl *= 0;
			if (p[j] != r){
				fr *= 1;
			} 
			else fr *= 0;
			
		}
		if (fl){
			cout << l << endl;
			return 0;
		}
		if (fr){
			cout << r << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3592
n = int(input())
a = list(map(int, input().split()))

xor = 0
count = 0
r = 0
for l in range(n):
    while r < n and xor & a[r] == 0:
        xor ^= a[r]
        r += 1
    count += r - l
    xor ^= a[l]
print(count)

Measured memory_bytes: 99820
function main(input) {
  const isUpperCase = (str) => {
    let arr = str.match(/^[A-Z]/);
    return arr ? true : false;
  };
  if (isUpperCase(input)) {
    console.log("A");
    return;
  } else {
    console.log("a");
    return;
  }
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));
// main("A");


Measured memory_bytes: 30624
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lop ios; ll t; cin>>t; while(t--)
#define pb push_back
#define vi vector<ll>
#define vivi vector<vector<ll>> 
#define vipa vector<pair<ll,ll>>
#define F first
#define S second
#define M 1000000007
#define kl "\n"
typedef long long ll;
ll lcm(ll x, ll y){ll k=x*y; k/=(__gcd(x,y)); return k;}
ll power(ll x,ll y){ ll r= 1;x = x % M;if(x==0) return 0; while(y>0) {if(y&1) r=(r*x)%M; y=y>>1; x=(x*x)%M;} return r;}  
void solve()
{ 
    ll k;
    cin>>k;
    ll a[10000000],dp[10000000];
  if(k%7==0)
    {
        k/=7;
    }
    
    for(ll i=0;i<10000000;i++)
    {
        a[i]=1;
    }
    
    dp[0]=a[0]%k;
    for(ll i=1;i<10000000;i++)
    {
        dp[i]=((10*dp[i-1])+a[i])%k;
    }
    ll ans=-2;
    for(ll i=0;i<10000000;i++)
    {
        if(dp[i]==0)
        {
            ans=i;
            break;
        }
    }
    cout<<ans+1<<kl;
}
int main() 
{ 
    //lop
    solve();
	return 0; 
} 




Measured memory_bytes: 159856
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
#include <cassert>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define MOD (long long int)(1e9+7)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  if(n <= 1e7){
    ret *= kaijo(n); ret %= MOD;
    ret *= gyaku_kaijo(r); ret %= MOD;
    ret *= gyaku_kaijo(n-r); ret %= MOD;
  }else{
    rep(i,r){
      ret *= n-i; ret %= MOD;
      ret *= mpow(r-i, MOD-2); ret %= MOD;
    }
  }
  return ret;
}

int main(void){
  fast_io
  cout<<fixed<<setprecision(15);
  int n,m;cin>>n>>m;
  int sum = 0;
  vector<int> A(n);
  rep(i,n){
    cin>>A[i];
    sum += A[i];
  }
  int kijun = (sum - 1) / (4*m);
  int count = 0;
  rep(i,n){
    if(A[i] <= kijun){

    }else{
      count++;
    }
  }
  if(count >= m){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
	int N;
	string s,t,ans="";
	cin >> N >> s >> t;
	for(int i=0;i<N;i++){
		ans.push_back(s[i]);
		ans.push_back(t[i]);
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD ((int)(1e9+7))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define float long double

int ans=0;

int32_t main()
{
	IOS
	int n,w;cin>>n>>w;
	vector<int>W(n),V(n);
	for(int i=0;i<n;i++)cin>>W[i]>>V[i];
	vector<int>dp(100000+1,1e15);dp[0]=0;
	//dp[i]  state : minimum waigth needed to make i value
	
	for(int i=0;i<n;i++)
	{
		//why two dps are takne ? because every elemnet get included maximum 1 times.
		vector<int>dp2=dp;
		for(int j=1;j<=100000;j++)
		{
			if( j-V[i] >=0 )dp2[j]=min(dp2[j],dp[j-V[i]]+W[i]);
		}
		dp=dp2;
	}
	int mx=0;
	for(int i=0;i<=100000;i++)
	{
		if(dp[i] <= w )mx=max(mx,i);
	}
	cout<<mx<<endl;
	
}
			
	
	
	
	
	

	

	

	
		


Measured memory_bytes: 1792
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    string t, s;
    cin >> t >> s;
    int nt = t.size(), ns = s.size();
    if(nt < ns) return 0;
    rep(i, nt-ns+1) {
        bool x = true;
        rep(j, ns) {
            if(t[i+j] != s[j]) x = false;
        }
        if(x) cout << i << endl;
    }
}


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

int main() {
  long long K, A, B; cin >> K >> A >> B;
  long long m, s;
  m = A-B, s = max(K-A, 0LL);
  if(s > 0) {
    if(m <= 0) {
      cout << -1 << endl;
    } else {
      cout << 1 + 2*((s+m-1)/m) << endl;
    }
  } else {
    cout << 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define CONCAT_(x,y) x##y
#define CONCAT(x,y) CONCAT_(x,y)
#define _v1 CONCAT(qyw1, __LINE__) // unique name in same line (otherwise use __COUNTER__)
#define _v2 CONCAT(qyw2, __LINE__)
#define forbits(i, m) for (int _v1 = m, i = __builtin_ctz(_v1); _v1 != 0; _v1 ^= _v1 & -_v1, i = __builtin_ctz(_v1))
#define forsubm(s, m) for (int s = m; s >= 0; s = !s ? -1 : m & (s - 1))
int __nextXZW(int v){int t=v|(v-1);int w=(t+1)|(((~t&-~t)-1)>>(__builtin_ctz(v)+1));return w;}
#define ksets(i, n, k) for (int i = (1u << k) - 1, max = i << (n - k); i <= max; i = __nextXZW(i))
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll N = 5e5+5, inf = 1e9+5000;
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mult(ll x, ll y) { return (x * y) % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, k; cin >> n >> k;
  vector<int> l(k), r(k);
  rep (i, k) cin >> l[i] >> r[i];

  vector<ll> dp(n+5);
  dp[0] = 0;
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1];
    for (int j = 0; j < k; j++) {
      if (i - l[j] < 1) continue;
      int max_r = min(i-1, r[j]);
      dp[i] = add(dp[i], sub(dp[i-l[j]], dp[i-max_r-1]));
    }
  }

  cout << sub(dp[n], dp[n-1]) << '\n';

  return 0;
}

Measured memory_bytes: 4772
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll solveA(){
    ll res = 0;
    ll A,B; cin >> A >> B;
    res = A*B - A - B + 1;
    return res;
}


ll solveB(){
    ll res = 0;
    ll N; cin >> N;
    if(N>=105) res++;
    return res;
}

ll solveC(){
    ll res = 0;
    string S; cin >> S; ll K; cin >> K;
    res = 1;
    for(int i = 0; S.length();i++){
        if(S[i] == '1') continue;
        else{
            res = S[i] - '0';
            break;
        }
    }
    return res;
}

ll solveD(){
    ll res = 0;
    ll N,M,Q; cin >> N >> M >> Q;
    vector<ll> L(M),R(M);
    vector<vector<ll>> G(N);
    for(int i = 0; i < M;i++){
        cin >> L[i] >> R[i]; L[i]--; R[i]--;
        G[L[i]].push_back(R[i]);
    }
    for(int i = 0; i < N;i++){
        sort(G[i].begin(),G[i].end());
    }
    while(Q--){
        ll p,q; cin >> p >> q;
        p--; q--;
        
        ll Ans = 0;
        for(ll x = p; x <= q;x++){
            Ans += (upper_bound(G[x].begin(), G[x].end(), q) - G[x].begin());
        }
        cout << Ans << endl;
    }
    return 0;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solveA() << endl;
    //cout << solveB() << endl;
    //cout << solveC() << endl;
    //solveD();
    return 0;
}


Measured memory_bytes: 256
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
  tmp=[]
  for val in cand[-1]:
    if val%10!=0:
      tmp.append(val*10+(val%10-1))
    tmp.append(val*10+(val%10))
    if val%10!=9:
      tmp.append(val*10+(val%10+1))
  cand.append(tmp)
ans=[]
for i in range(len(cand)):
  for val in cand[i]:
    ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Measured memory_bytes: 15144
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
P dp[101][50001];

void Max(P &a,P b){a=max(a,b);}

int main(){
  int n,p[101];
  while(cin>>n,n){
    for(int i=0;i<n;i++)cin>>p[i];
    
    memset(dp,-1,sizeof(dp));
    dp[0][0]=P(0,0);
  
    for(int i=0;i<n;i++)
      for(int j=0;j<n*500;j++){
	if(dp[i][j]==P(-1,-1))continue;
	int coin=dp[i][j].first, ncost=dp[i][j].second-p[i];
	Max(dp[i+1][j],dp[i][j]);
	if(p[i]%1000<500&&p[i]%1000)Max(dp[i+1][j+(500-p[i]%500)],P(coin+1,ncost));
	if(p[i]%1000==0&&j>=500) Max(dp[i+1][j-500],P(coin+1,ncost));
	
	if(p[i]%1000>=500) {
	  if(j>=p[i]%500)Max(dp[i+1][j-p[i]%500],P(coin+1,ncost));
	  else Max(dp[i+1][j+(500-p[i]%500)],P(coin,ncost));
	}
      }
    
    P ans=P(0,0);
    for(int i=0;i<50000;i++)Max(ans,dp[n][i]);
    cout <<ans.first<<" "<<-ans.second<<endl;
    
  }	
  return 0;
}

Measured memory_bytes: 42480
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n,m;
  cin >> n >> m;
  vector<P> v;
  ll c[n];
  mem(c);
  REP(i,1,n+1) {
    REP(j,i+1,n+1) {
      v.pb(P(i,j));
      c[i]++;
      c[j]++;
    }
  }
  vector<P> ans;
  rep(i,v.size()) {
    if(m&&c[v[i].F]>1&&c[v[i].S]>1) {
      m--;
      c[v[i].F]--;
      c[v[i].S]--;
    } else ans.pb(v[i]);
  }
  if(m) pr(-1);
  else {
    pr(ans.size());
    rep(i,ans.size()) pr(ans[i].F,ans[i].S);
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    int K; cin >> K;
    int A; cin >> A;
    int B; cin >> B;

    bool can = false;
    rrep(i, 1, 1000) {
        int kb = i * K;
        if (A <= kb && kb <= B) {
            can = true;
            break;
        }
    }

    if (can) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3676
#include <iostream>

using namespace std;

void solve()
{
	int n;
	cin >> n;
	while(n--)
	{
		int X, Y, W, H;
		cin >> X >> Y >> W >> H;
		int num;
		cin >> num;
		int count = 0;
		for(int i = 0; i < num; ++i)
		{
			int x, y;
			cin >> x >> y;
			if((X <= x && x <= X + W) && (Y <= y && y <= Y + H))
			{
				count++;
			}
		}
		cout << count << endl;
	}
}

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

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
#define F first
#define S second
#define mod 1000000007
#define pb push_back
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define REV(i,a,n) for(int i=a;i>=n;i--)
#define all(a) a.begin(),a.end()
const int NUM = 2e5 + 5;

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int num_tests=1; 
    //cin >> num_tests;
    while(num_tests-->0){
        int a,b,c; cin >> a >> b >> c;
        if(a == b and a == c){
            cout << "Yes";
        }
        else cout << "No";
    }    
}

Measured memory_bytes: 3552
#include<bits/stdc++.h>
using namespace std;
                    
                    
int main(){
    int N, AC, WA, TLE, RE;
    string S;
    cin >> N;
    AC = WA = TLE = RE = 0;
    for(int i = 0; i < N; i++) {
        cin >> S;
        if (S == "AC") {
            AC++;
        } else if (S == "WA") {
            WA++;
        } else if (S == "TLE") {
            TLE++;
        } else if (S == "RE") {
            RE++;
        }
    }

    cout << "AC x " << AC << endl;
    cout << "WA x " << WA << endl;
    cout << "TLE x " << TLE << endl;
    cout << "RE x " << RE << endl;
}

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

int main (){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int x = 0;
    int ans = 0;
    rep(i,s.length()){
        if(s[i] == 'I') x++;
        else x--;
        ans = max(ans,x);
    }
    cout << ans << endl;
    return 0;
}

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

class State{
public:
  int x, y, cost;

  State(int _x, int _y, int _cost){
    x = _x;
    y = _y;
    cost = _cost;
  }
};

int h, w, n;
int cx[12], cy[12];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool closed[1002][1002];
char t[1002][1002];

int bfs(int sx, int sy, int gx, int gy){
  queue<State> open;
  open.push(State(sx, sy, 0));
  memset(closed, 0, sizeof(closed));

  while(!open.empty()){
    State st = open.front();
    open.pop();

    if(closed[st.y][st.x]) continue;
    closed[st.y][st.x] = true;

    if(st.x == gx && st.y == gy){
      return st.cost;
    }

    for(int i = 0; i < 4; i++){
      int nx = st.x + dx[i];
      int ny = st.y + dy[i];

      if(0 <= nx && nx < w && 0 <= ny && ny < h && t[ny][nx] == '.'){
        open.push(State(nx, ny, st.cost + 1));
      }
    }
  }

  return 99999999;
}

int main(){
  while(cin >> h >> w >> n){
    for(int i = 0; i < h; i++){
      cin >> t[i];

      for(int j = 0; j < w; j++){
        if(t[i][j] == 'S'){
          cx[0] = j;
          cy[0] = i;
          t[i][j] = '.';
        }
        else if('0' <= t[i][j] && t[i][j] <= '9'){
          int idx = t[i][j] - '0';
          cx[idx] = j;
          cy[idx] = i;
          t[i][j] = '.';
        }
      }
    }

    int ans = 0;

    for(int i = 1; i <= n; i++){
      ans += bfs(cx[i - 1], cy[i - 1], cx[i], cy[i]);
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 2840
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */

public class Main {
    public static void main(String[] args) {
        InputStream    inputStream    = System.in;
        OutputStream outputStream = System.out;
        InputReader    in                      = new InputReader(inputStream);
        PrintWriter      out                    = new PrintWriter(outputStream);
        Task                 solver               = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
        	int x1 = in.nextInt();
        	int y1 = in.nextInt();
        	int x2 = in.nextInt();
        	int y2 = in.nextInt();
        	
        	int X = x2 - x1;
        	int Y = y2 - y1;
        	
        	out.printf("%d %d %d %d", x2 - Y , y2 + X, x1 - Y, y1 + X);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 22996
#include <iostream>
using namespace std;
int main(){
    int a[5],min=10,ans;
    for(int i=0;i<5;i++){
        cin>>a[i];
        if(a[i]%10&&a[i]%10<min) min=a[i]%10;
        if(a[i]%10) ans+=(a[i]/10+1)*10;
        else ans+=a[i];
    }
    ans-=10-min;
    cout<<ans<<endl; 
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        x: i64,
    }

    let ans = match x {
        400..=599 => 8,
        600..=799 => 7,
        800..=999 => 6,
        1000..=1199 => 5,
        1200..=1399 => 4,
        1400..=1599 => 3,
        1600..=1799 => 2,
        1800..=1999 => 1,
        _ => 0,
    };

    println!("{}", ans);
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;
priority_queue<int,vector<int>,greater<int>> que;
     signed main(){
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];

sort(a,a+n);

for(int i=n-1;i>=0;i--)if(que.size()<k&&a[i]>0)que.push(a[i]);
if((que.size()==0&&k%2==1)||n==k){
int ans2=1;
for(int i=0;i<k;i++){ans2=(ans2*(MOD+a[n-1-i])%MOD)%MOD;}
cout<<ans2<<endl;
return 0;
}
if(que.size()<k&&(k-que.size())%2==1)que.pop();
int x=0;
for(int i=0;i*2+1<n;i++){
   // cerr<<x<<' ';
   if(que.size()+x==k&&que.size()<=1)break;
    if(a[i*2]<=0&&a[i*2+1]<=0){
        if(que.size()+x<k){
            x+=2;
            
            continue;
        }
        int p=que.top();
        que.pop();
        if(p*que.top()<a[i*2]*a[i*2+1]){
            que.pop();
            x+=2;
            continue;
        }else{
            que.push(p);
            break;
        }
    }
}
int ans=1;
for(int i=0;i<x;i++)ans=(ans*(-1*a[i]))%MOD;
while(!que.empty()){
  //  cerr<<que.top()<<endl;
    ans=(ans*que.top())%MOD;
    que.pop();
}
cout<<ans<<endl;

     }


 


 






    





      

        


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

int ctoi(char c){
    switch (c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default: return 0;
    }
}

int main(){
    int N;
    cin >> N;
    int fx = 0;
    string ns = to_string(N);
    int len = ns.size();
    rep(i,len){
        fx += ctoi(ns[i]);
    }
    if(N % fx == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ll long long
#define P pair<int,int>
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
const int INF = 2002002002;
const ll LLINF = 9009009009009009009;
using namespace std;

int main() {
    fast_io
    int n, m;
    cin >> n >> m;
    ll a;
    priority_queue<ll> q;
    rep(i,n) {
        cin >> a;
        q.push(a);
    }
    rep(i,m) {
        a = q.top();
        q.pop();
        a /= 2;
        q.push(a);
    }
    ll ans = 0;
    while(!q.empty()) {
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
    return 0;
}   

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main(){
    string S;
    int Q;
    cin >> S >> Q;
 
    int T[Q];
    int F[Q];
    char C[Q];
    int cnt = 0;
 
    rep(i, Q){
        cin >> T[i];
        if (T[i] == 1){
            cnt++;
        }
        if (T[i] == 2){
            cin >> F[i] >> C[i];
            if ( ( (F[i] == 1) && (cnt % 2 == 1) ) || ( (F[i] == 2) && (cnt % 2 == 0) )  ){
                S += C[i];
            }
        }
    }

    reverse(S.begin(), S.end());
    cnt = 0;

    rep(i, Q){
        if (T[i] == 1){
            cnt++;
        }
        if (T[i] == 2){
            if ( ( (F[i] == 1) && (cnt % 2 == 0) ) || ( (F[i] == 2) && (cnt % 2 == 1) )  ){
                S += C[i];
            }
        }
    }
 
    if (cnt % 2 == 0) reverse(S.begin(), S.end());
 
    cout << S << endl;
 
 
    return 0;
}


Measured memory_bytes: 2692
N, Q = map(int, input().split())
s = input()
query = []
for i in range(Q):
    t, d = input().split()
    query.append([t, d])


def onequery(number):
    bool = True
    for i in range(Q):
        if s[number-1] == query[i][0]:
            if query[i][1] == "R":
                number += 1
            else:
                number -= 1
        if number <= 0 or number >= N+1:
            bool = False
            return bool
    return bool


left = 0
right = N+1
while right - left > 1:
    mid = left + (right - left) // 2
    if onequery(mid):
        right = mid
    else:
        left = mid
leftans = right


left = 0
right = N + 1
while right - left > 1:
    mid = left + (right - left) // 2
    if not onequery(mid):
        right = mid
    else:
        left = mid

rightans = left
if rightans - leftans <= 0:
    print(0)
else:
    print(rightans - leftans + 1)

Measured memory_bytes: 89804
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer[] arr = new Integer[3];
        int total = 0;
        for(int i = 0; i < 3; i++) {
            arr[i] = sc.nextInt();
            total += arr[i];
        }
        Arrays.sort(arr, Collections.reverseOrder());

        int cnt = 0;
        while(total%3!=0 || arr[0]*3>total) {
            cnt++;
            total+=2;
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 35896
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<lint,lint> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//map<lint,deque<lint> > me,m2;
//map<lint,set<lint> > me,m2;
map<lint,vector<lint> > me,m2;
vector<pint> v;
int x[114514],y[114514];
bool aru[114514];
int n;lint d;
void cal(void)
{
	lint out=0;
	rep(i,n){
		if(aru[i]) v.pb(mp(x[i],y[i]));
	}
	sort(All(v));
	rep(i,v.size()){
		lint d1=v[i].fi-v[i].se,d2=v[i].fi+v[i].se;
		vector<lint> s1=me[d1-d],s2=m2[d2-d];
		//printf("(%d)\n",i);
		//rep(j,s1.size()) cout<<s1[j]<<' ';cout<<endl;
		//rep(j,s2.size()) cout<<s2[j]<<' ';cout<<endl;
		if(s1.size()>0){
			int num=(s1.end()-lower_bound(All(s1),v[i].se));
			//printf("[%d]\n",num);
			out+=num;
		}
		if(s2.size()>0){
			int num=(s2.end()-upper_bound(All(s2),-v[i].se));
			//printf("[%d]\n",num);
			out+=num;
		}
		me[d1].pb(v[i].se);m2[d2].pb(-v[i].se);
	}
	cout<<out<<endl;
}
map<lint,set<pint> > n1,n2;
queue<int> q;
void add(int it){
	if(aru[it]) return;
	q.push(it);aru[it]=true;
	n1[x[it]+y[it]].erase(mp(y[it],it));
	n2[x[it]-y[it]].erase(mp(y[it],it));
}
int main()
{
	int a,b;
	scanf("%d %d %d",&n,&a,&b);
	rep(i,n){
		scanf("%d %d",&x[i],&y[i]);
		n1[x[i]+y[i]].insert(mp(y[i],i));
		n2[x[i]-y[i]].insert(mp(y[i],i));
	}
	memset(aru,false,sizeof(aru));
	a--;b--;
	d=abs(x[a]-x[b]);d+=abs(y[a]-y[b]);
	add(a);add(b);
	int num=0;
	while(!q.empty()){
		int it=q.front();q.pop();
		lint d1=x[it]+y[it],d2=x[it]-y[it];
		//cout<<it<<' '<<d1<<' '<<d2<<endl;
		set<pint> &s11=n1[d1-d],&s12=n1[d1+d];
		set<pint>::iterator It;
		vector<int> vi;
		if(s11.size()>0){
			It=s11.lower_bound(mp(y[it]-d,-114514));
			while(It!=s11.end() && (*It).fi<=y[it]){
				//add((*It).se);It++;
				vi.pb((*It).se);It++;
			}
		}
		if(s12.size()>0){
			It=s12.lower_bound(mp(y[it],-114514));
			while(It!=s12.end() && (*It).fi<=y[it]+d){
				//add((*It).se);It++;
				vi.pb((*It).se);It++;
			}
		}
		
		set<pint> &s21=n2[d2-d],&s22=n2[d2+d];
		if(s21.size()>0){
			It=s21.lower_bound(mp(y[it],-114514));
			while(It!=s21.end() && (*It).fi<=y[it]+d){
				//add((*It).se);It++;
				vi.pb((*It).se);It++;
			}
		}
		if(s22.size()>0){
			It=s22.lower_bound(mp(y[it]-d,-114514));
			while(It!=s22.end() && (*It).fi<=y[it]){
				//add((*It).se);It++;
				vi.pb((*It).se);It++;
			}
		}
		rep(i,vi.size()) add(vi[i]);
		num+=vi.size();
	}
	cal();
}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

signed main(){

	lli data[3];
	REP(i,0,3)data[i]=0;

	lli a,b;
	cin>>a>>b;
	data[a-1]++;
	data[b-1]++;

	REP(i,0,3){
		if(data[i]==0)cout<<i+1<<endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <list>
using namespace std;

int main(){
    string K;

    cin >> K;

    bool check = false;
    for(int i=0; i<3; i++){
        if(K[i] == '7')
            check = true;       
    }

    if(check)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3620
a,b = map(int,input().split())
cards = [2,3,4,5,6,7,8,9,10,11,12,13,1]
a_card = cards.index(a)
b_card = cards.index(b)
if a_card > b_card:
    print('Alice')
elif a_card < b_card:
    print('Bob')
else:
    print('Draw')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=0;
	double d;
	cin >> n >> d;
	for(int i=1;i<=n;i++)
	{
		double tmp1,tmp2;
		cin>>tmp1>>tmp2;
		double a = sqrt((tmp1*tmp1+tmp2*tmp2));
		if(a<=d)
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3836