akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pb push_back
#define ifr(a, value) insert(a.begin(), value)
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define szz(v) ((int)(v).size())  
#define vi vector<int>
#define vll vector<ll>
#define str string
#define fr(i, j, k) for(i = j; i < k; i++)
#define bk(i, j, k) for(i = j; i >= k; i--)
#define frit(a, it) for(__typeof((a).begin()) it = a.begin(); it != a.end(); ++it)
#define mem(ptr)  memset(ptr, 0, sizeof ptr)        // use fill() for value other than 0 //
#define rtn return 
#define clk fprintf(stderr, "\nTIME = %lf\n", 1.0 * clock()/CLOCKS_PER_SEC)
#define nl "\n"
#define inf 1LL<<61
#define dbg(x) (cerr << #x << ": " << x << "\n")
const long long mod = 1e9+7;

ll gcd(ll a,ll b) { return b==0 ? a : gcd(b, a%b); }   // no need to swap a, b, it auto. happens after first call //
ll expo(ll x, ll y){ ll res = 1; x = x % mod;  while (y > 0) { if (y & 1)res = (res*x) % mod; y = y>>1;x = (x*x) % mod;}return res;}
void matmul(ll a[][2], ll b[][2]) { ll tmp[2][2]; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { tmp[i][j] = 0; for(int k=0; k<2; k++) tmp[i][j] = (tmp[i][j] + a[i][k]*b[k][j]) % mod; }} for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = tmp[i][j]; }
ll fibo(int n)    // returns nth fibonacci number, also S(n) = f(n+2)-1
{ if(n == 0) return 0; else if(n == 1) return 1; ll T[2][2] = { {0, 1} , {1, 1} }; ll res[2][2] = { {1, 0}, {0,1} }; n--; while(n) { if(n & 1) matmul(res, T); n >>= 1; matmul(T, T); } return res[1][1]; }

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    str s;
    cin >> s;
    int cur = 0, ans;
    for(int i=0; i<n; i++)
    {
        cur += (s[i] == 'E');
    }
    ans = cur;                         // min at this instant will be either alleast (for s[0] = w) or alleast-1 (for s[0] = E)
    for(int i=0; i<n; i++)
    {
        if(s[i] == 'E') cur--;
        else cur++;
        ans = min(ans, cur);
    }
    cout << ans;
    return 0;
}
// at nay moment count east from right side, west from left side..

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

int main(void) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }
    int sh = 1;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a.at(i) != sh) {
            cnt++;
        }
        else {
            sh++;
        }
    }
    if (cnt == n) {
        cout << -1 << endl;
    }
    else {
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 4052
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    left = [0] * (N + 1)
    right = [0] * (N + 1)

    # 予めGCDを計算する
    for i in range(N):
        # 左から累積したGCD
        left[i+1] = math.gcd(left[i], A[i])
    for i in reversed(range(N)):
        # 右から累積したGCD
        right[i] = math.gcd(right[i+1], A[i])

    ret = 0
    for i in range(N):
        ret = max(ret, math.gcd(left[i], right[i+1]))
    print(ret)

    
if __name__ == '__main__':
    main()


Measured memory_bytes: 21448
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int a1, a2, a3, a4, a5, a6, a7, b1, b2, b3, b4, b5, b6, b7, c1, c2, c3, c4, c5, c6, c7;
    scanf("%d %d\n%d %d\n%d %d\n%d %d\%d %d\n%d %d\n%d %d\n", &a1, &b1, &a2, &b2, &a3, &b3, &a4, &b4, &a5, &b5, &a6, &b6, &a7, &b7);
    c1 = a1 - b1;
    c2 = a2 - b2;
    c3 = a3 - b3;
    c4 = a4 - b4;
    c5 = a5 - b5;
    c6 = a6 - b6;
    c7 = a7 - b7;
    printf("%d\n%d\n%d\n%d\n%d\n%d\n%d\n", c1, c2, c3, c4, c5, c6, c7);
    return 0;
}

Measured memory_bytes: 600
N=int(input())
uvw=[list(map(int,input().split())) for _ in range(N-1)]
q=[[] for _ in range(N)]
max=10**15
dist=[0]+[max for i in range(N-1)]
for i in range(N-1):
    q[uvw[i][0]-1].append((uvw[i][1]-1,uvw[i][2]))
    q[uvw[i][1]-1].append((uvw[i][0]-1,uvw[i][2]))
now=0
now_d=0

while(True):
    if q[q[now][-1][0]]==[]:
        q[now].pop()
        if q[now]==[]:
            break
    if dist[q[now][-1][0]]!=max:
        if len(q[now])!=1:
            q[now]=[q[now][-1]]+q[now][:-1]
    posi=q[now][-1]
    if dist[posi[0]]==max:
        dist[posi[0]]=now_d+posi[1]
    now_d=dist[posi[0]]
    q[now].pop()
    now=posi[0]
    posi=q[posi[0]][0]
for i in range(N):
    if dist[i]%2==0:
        print(0)
    else:
        print(1)

Measured memory_bytes: 62004
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <map>
#include <cmath>
#include <bitset>
#include <deque>
#define MAX_N 100
#define MAX_T 200
#define INF (1LL<<31)
#define fst first
#define snd second
typedef long long ll;
typedef std::pair<int,int> ii;
using namespace std;
  
ll N,M,R;
ll r[8];
ll d[201][201]={};
ll ans=INF;
bool used[8]={};
int root[8];

void dfs(int dep){
  if(dep==R){
    ll temp=0;
    for(int i=0;i<R-1;i++){
      temp+=d[root[i]][root[i+1]];
    }
    ans=min(ans,temp);
    return;
  }
  for(int i=0;i<R;i++){
    if(!used[i]){
      root[dep]=r[i];
      used[i]=true;
      dfs(dep+1);
      used[i]=false;
    }
  }
  return;
}
int main(){
  cin>>N>>M>>R;
  for(int i=0;i<R;i++){
    cin>>r[i];
  }
  for(int i=1;i<N;i++){
    for(int j=i+1;j<=N;j++){
      d[i][j]=d[j][i]=INF;
    }
  }
  for(int i=0;i<M;i++){
    ll a,b, c;
    cin>>a>>b>>c;
    d[a][b]=d[b][a]=c;
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<N;j++){
      if(i==j)continue;
      for(int k=j+1;k<=N;k++){
        if(i==k)continue;
        d[j][k]=min(d[j][k], d[j][i]+d[i][k]);
        d[k][j]=d[j][k];
      }
    }
  }
  dfs(0);
  cout<<ans<<endl; 
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<math.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

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


Measured memory_bytes: 256
using System;
 
namespace aaaa
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var str = Console.ReadLine();
          if (str[2] == str[3] && str[4] == str[5])
            Console.Write("Yes");
          else
            Console.Write("No");
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <stdio.h>
using namespace std;

int fa[100005];
int ax[100005];
int n;

int main()
{
    int i,all=0,b=0,low=100000;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&ax[i]);
        fa[ax[i]]++;
        all = max(all,ax[i]);
        low = min(low,ax[i]);
    }
    if(all-low>1){
            printf("No");
            return 0;
    }
    if(all==low){
        if(all==n-1||all*2<=n)printf("Yes");
        else printf("No");
        return 0;
    }
    for(i=0;i<n;i++){
        if(ax[i]!=all)b++;
    }
    if(b>=all||(all-b)*2+b>n)printf("No");
    else printf("Yes");
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
/*
*****************code written By**********************
..................Marajul islam.......................
...................BSMRSTU,CSE........................
*/ 
 
int sc1() {int x; scanf("%d", &x); return x;}
 
long long sc2() {long long x; scanf("%lld", &x); return x;}
 
 
 
#define  gcd(a,b)         __gcd(a,b)
#define  lcm(a,b)         (a*b)/gcd(a,b)
#define  Int              sc1()
#define  LL               sc2()
#define  For(n)           for(int i=0;i<n;i++)
#define  Forj(n)          for(int j=0;j<n;j++)
#define  Fork(n)          for(int k=0;k<n;k++)
#define  For1(n)          for(int i=1;i<=n;i++)
#define  ll               long long
#define  vi               std::vector<int>
#define  vll              std::vector<ll>
#define  qui              qu
#define  pb               push_back
#define  mpsi             std::map<string, int>
 
 
const int mod           = 1e9 + 7;
const int inf           = (int)2e9 + 5;
const ll  Inf           = (ll)1e18 + 5;
const int N             = 5e6 + 5;
 
inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll)a * b % mod;}
 

 
 
int solve() {
 
	ll n,a,b;
	cin>>n>>a>>b;
	if(a==0){
		cout<<0<<endl;
		return 0;
	}
	// else if(b==0){
	// 	cout<<n<<endl;
	// 	return 0;
	// }
	ll ans=(n/(a+b))*a;
	if(ans==0) {cout<<min(a,n)<<endl;return 0;}
	ans+=min(a,(n%(a+b)));
	cout<<ans<<endl;
 
	return 0;
}
 
 
 
 
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
 
	int test = 1, tc = 0;
	//scanf("%d", &test);
	//cin >> test;
	while (test--) {
		//printf("Case %d: ", ++tc);
		solve();
	}
 
	return 0;
 
 
 
 
}




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

using namespace std;

int main() {
    int N; long long W;
    cin >> N >> W;

    vector<long long> val[4];

    long long w, v;
    cin >> w >> v;
    long long w0 = w;
    val[0].push_back(v);

    for (int i = 1; i < N; i++) {
        cin >> w >> v;

        int rem = w - w0;
        val[rem].push_back(v);
    }

    for (int i = 0; i < 4; i++) {
        sort(val[i].begin(), val[i].end(), greater<long long>());
        for (int j = 1; j < val[i].size(); j++) {
            val[i][j] = val[i][j - 1] + val[i][j];
        }
    }

    for (int i = 0; i < 4; i++) {
        val[i].insert(val[i].begin(), 0);
    }

    long long ans = 0;
    for (int i = 0; i < val[0].size(); i++) {
        for (int j = 0; j < val[1].size(); j++) {
            for (int k = 0; k < val[2].size(); k++) {
                for (int l = 0; l < val[3].size(); l++) {
                    long long sum = w0*i + (w0 + 1)*j + (w0 + 2)*k + (w0 + 3)*l;
                    if (sum <= W) {
                        ans = max(ans, val[0][i] + val[1][j] + val[2][k] + val[3][l]);
                    }
                }
            }
        }
    }

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
#define ll long long

int n;
int h;
int a[114514];
int b[114514];
int d[114514];
int ans;
int main() {
	cin >> n >> h;
	int max_a = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		max_a = max(a[i], max_a);
	}
	int j = 0;
	for (int i = 0; i < n; i++) {
		if (b[i] > max_a) {
			d[j] = b[i];
			j++;
		}
	}
	sort(d, d + j);
	for (int i = j - 1; i >= 0; i--) {
		ans++;
		h = h - d[i];
		if (h <= 0) {
			cout << ans << endl;
			return 0;
		}
	}
	while (true) {
		ans++;
		h = h - max_a;
		if (h <= 0) {
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    vector<int>let={a,b,c};
    sort(let.begin(),let.end());
    if(let.at(0)==5&&let.at(1)==5&&let.at(2)==7){puts("YES");}
    else{puts("NO");}
    return 0;}

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

int n, a[100001], b[100001];
int main() {
	scanf("%d",&n);
	for(int i = 0; i < n; i++) scanf("%d%d",a+i,b+i);
	long long curr = 0;
	for(int i = n-1; i >= 0; i--) {
		curr += ((a[i]+curr)%b[i] ? b[i]-(a[i]+curr)%b[i] : 0);
	}
	printf("%lld\n", curr);
}


Measured memory_bytes: 1152
#include <iostream>
#include <string>

using namespace std;

string s,t;
int N;
long long mod = 1e9 + 7;
long long p = 1;

int main(){
  cin >> N;
  cin >> s;
  cin >> t;
  int ptr = 0;
  if(s[0] == t[0]){
    p *= 3;
    ptr += 1;
  }else{
    p *= 6;
    ptr += 2;
  }
  while(ptr < N){
    if(s[ptr]==t[ptr]){
      if(s[ptr-1]==t[ptr-1]) p *= 2;
      ptr++;
    }else{
      if(s[ptr-1]==t[ptr-1]) p *= 2;
      else p *= 3;
      ptr += 2;
    }
    p %= mod;
  }
  cout << p << endl;
  return 0;
}




Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n[5],i;
    for(i=1;i<=4;i++)
    scanf("%1d",&n[i]);
    if(n[1]==n[2]&&n[2]==n[3])
    {printf("Yes\n");
    return 0;}
    if(n[2]==n[3]&&n[3]==n[4])
    {printf("Yes\n");
    return 0;}
    printf("No\n");
    return 0;
}

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

using ll = long long;
using ul = unsigned long;
using ull = unsigned long long;
#define vec vector
#define rep(_i,_n) for(ll _i = 0; _i < _n; _i++)
#define rep2(_i,_s,_n) for(ll _i = _s; _i < _n; _i++)
#define elif else if
#define push(_a) push_back(_a)
#define fullSort(_a) sort(_a.begin(), _a.end())
#define inputVecI(_name, _n) vec<int> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecL(_name, _n) vec<long> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecLL(_name, _n) vec<ll> _name(_n);rep(_i, _n)cin >> _name[_i];
#define inputVecS(_name, _n) vec<string> _name(_n);rep(_i, _n)cin >> _name[_i];
#define findMaxIdx(_name) distance(_name.begin(), max_element(_name.begin(), _name.end()))
#define printVec(_vec) cout << "{";rep(i, _vec.size()-1)cout << _vec[i] << ",";cout << _vec[_vec.size()-1];cout << "}\n";
#define append(_x) push_back(_x)
#define mapLoop(_i, _name) for(auto i = _name.begin(); i != _name.end(); i++)


int main()
{
    int N, K;
    cin >> N >> K;
    vec <int> S(N, 1);
    for(int i = 0; i < K; i++){
      int buf;
      cin >> buf;
      rep(j, buf){
        int A;
        cin >> A;
        S[A - 1] = 0;
      }
    }
    int ans = 0;
    rep(i, N){
      if(S[i] == 1)ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

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

	int X, Y; cin >> X >> Y;
	for (int a = 0; a <= X; a++) {
		int b = X - a;
		if (a * 2 + b * 4 == Y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>
#include <functional>

typedef long long ll;
using namespace std;


int main(){
    int n, k;
    cin >> n >> k;
    ll a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    bool ans[n - k];
    for(int i = 0; i < n - k; i++){
        ans[i] = false;
    }
    for(int i = k; i <= n - 1; i++){
        if(a[i] > a[i - k]) ans[i - k] = true;
    }
    for(int i = 0; i < n - k; i++){
        if(ans[i]){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 5344
main = do
  li <- getLine
  let n = read li
  let ans = compute n
  print ans

compute :: Int -> Int
compute n = minimum
    [ f k p
    | k <- takeWhile (\k -> k*k <= n) [1..]
    , let (p,q) = divMod n k
    , q == 0 ]

ketas = iterate (10 *) 1
keta n = length $ takeWhile (n >=) ketas

f a b = max (keta a) (keta b)


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int main() {
  string s;
  cin >> s;
  set<char> c;

  for (int i = 0; i < s.size(); i++)
    c.insert(s[i]);

  if (c.size() == 26)
    cout << "None" << endl;

  for (char i = 'a'; i <= 'z'; i++) {
    if (c.count(i) == 0) {
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program {
    static void Main(string[] args) {
        //入力
        string S = Console.ReadLine();

        //Sの文字数
        int length = S.Length;

        //出力
        if (CountChar(S, 'o')　>= length - 7) {
            Console.WriteLine("YES");
        } else {
            Console.WriteLine("NO");
        }

    }


    // 文字の出現回数をカウント
    public static int CountChar(string s, char c) {
        return s.Length - s.Replace(c.ToString(), "").Length;
    }

}

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

int main(){
  string s;
  cin>>s;
  int a=(s[0]-'0')*10+(s[1]-'0');
  int b=(s[2]-'0')*10+(s[3]-'0');
  bool YYMM=(b>=1&&b<=12);
  bool MMYY=(a>=1&&a<=12);
  if(YYMM){
    if(MMYY) cout<<"AMBIGUOUS"<<endl;
    else cout<<"YYMM"<<endl;
  }
  else if(MMYY) cout<<"MMYY"<<endl;
  else cout<<"NA"<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = b - a;
		int height = 0;
		for (int i = x; i >= 0; i--) {
			height += i;
		}
		System.out.println(height - b);
	}
}

Measured memory_bytes: 23636
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>
#include <set>   
#include <bitset>
//#include <boost/math/common_factor_rt.hpp>

#define ll long long

int L = 1000000007;
using namespace std;

int main()
{
	ll n;
	ll a[100050] = {};

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	sort(a, a + n);

	if (n % 2 == 0) {
		for (int i = 0; i < n; i+= 2)
		{
			if (a[i] != a[i + 1]) {
				cout << 0 << endl;
				return 0;
			}
		}
	}
	else {
		for (int i = 1; i < n; i += 2)
		{
			if (a[i] != a[i + 1]) {
				cout << 0 << endl;
				return 0;
			}
		}
	}

	int res = 1;
	for (int i = 0; i < n / 2; i++) {
		res *= 2;
		res %= L;
	}

	cout << res << endl;
}

int dsum(ll a) {
	int ans = 0;
	while (a != 0) {
		ans += a % 10;
		a /= 10;
	}
	return ans;
}


Measured memory_bytes: 1024
# A - Shik and Stone
import sys
sys.setrecursionlimit(10**7)
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    # まず右に進もうとする
    nxt_h = h 
    nxt_w = w + 1   
    # 右が壁か範囲外なら下に進む
    if  not(-1<nxt_w<W) or mp[nxt_h][nxt_w] == '.':
        nxt_h = h + 1
        nxt_w = w 
    # 下も行き止まりならスルー
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)
        
dfs(0,0)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '#':
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Measured memory_bytes: 9208
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 1000000007
#define N 100005
#define PI 3.14159265
bool compare(pair<ll,char> i, pair<ll,char> j) 
{
  return i.S < j.S;
}
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
}
int main()
{
	ios
	ll n,m;
	cin>>n>>m;
	cout<<n*(n-1)/2+m*(m-1)/2;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
for i in range(1, n + 1):
    if i % 3 == 0:  #3の倍数か
        print(" " + str(i), end="")
    else:
        x = i
        while x > 0:
            if x % 10 == 3:  #3が付く数か
                print(" " + str(i), end="")
                break
            x //= 10
print()    


Measured memory_bytes: 5872
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

// 0からnまでの論理和
ll XOR(ll n) {
	ll res = 0;
	ll i = 2;
	while (i <= 2*n) {
		ll num = (n / i)*(i / 2); // 1の個数
		if (n%i >= i / 2) num += (n%i) - (i / 2) + 1;
		res += (i / 2) * (num % 2 == 1);
		i *= 2;
	}
	return res;
}

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

	ll A, B;
	cin >> A >> B;

	// cout << XOR(A) << endl;

	ll C = XOR(A - 1);
	ll D = XOR(B);

	ll ans = D ^ C;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////


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

    b -=a;
    ll ans = 0;
    rep(i,0,b)ans += i;
    P(ans - a);
    return  0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
status=0#0:不明、1:増加、2:減少
count=0
for i in range(1,N):
    if status==0:
        if A[i-1]<A[i]:
            status=1
        elif A[i-1]>A[i]:
            status=2
        else:
            pass
    elif status==1:
        if A[i-1]>A[i]:
            count+=1
            status=0
    else:
        if A[i-1]<A[i]:
            count+=1
            status=0
print(count+1)    

Measured memory_bytes: 14228
#include <bits/stdc++.h> //全てのヘッダファイルをインクルード
 
//ループ
#define rep(i, n) for(int i = 0; i < (n); i++) //普通のループ
#define repr(i, n) for(int i = n; i >= 0; i--) //逆ループ
 
//型名省略
typedef long long ll;
//値
static const ll MX = 100005;
static const ll MX_ll = 1e18;
const double PI = acos(-1); //π
 
using namespace std;
 
//ソート
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
 
//#include "./lib/generic/search.h"

//文字列入力した小数値を小数点なくして返す
int changeDoubleToInt(string decimal){ 
    decimal.erase(1, 1); //小数点削除
    int n_decimal = atoi(decimal.c_str()); //c_strでchar*に変換後、atoiでintに変換
    return n_decimal;
}

//最大公約数
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

//素数判定(True/Falseを返却)
int IsPrime_tf(ll num){
    if (num < 2) return false; //0、1は素数でない
    else if (num == 2) return true; //2は素数
    else if (num%2==0) return false; // 偶数はあらかじめ除く
    for (ll i = 3; i*i <= num; i += 2){ //チェックは2～√nで十分
        if (num % i == 0) return false; //素数でない
    }
    return true; //素数である
}

//素数判定(割れる値を返却)
ll IsPrime_value(ll num){
    if (num < 2) return -1; //0、1は素数でない
    else if (num == 2) return 2; //2は素数
    for (ll i = 2; i*i <= num; i += 1){ //チェックは2～√nで十分
        if (num % i == 0) return i; //素数でない
    }
    return num; //素数である
}

int main(){
   char s;
   int ans = 0, tmp_ans=0;
   rep(i,3){
       cin >> s;
       if(s=='R'){
           tmp_ans++;
       }else{
           if(tmp_ans>ans) ans = tmp_ans;
           tmp_ans=0;
       }
       //cout << " " << ans << " " << tmp_ans << endl;
   }
   if(tmp_ans>ans) ans = tmp_ans;
   cout << ans << endl;
}

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

using namespace std;

int n,m,i,j,d[3010][3010];
char s[3010],t[3010];


void recons(int lungime,int p1,int p2)
{
    if(lungime>0)
    {
        if(s[p1-1]==t[p2-1])
        {
            recons(lungime-1,p1-1,p2-1);
            cout<<s[p1-1];
        }
        else
        {
            if(d[p1-1][p2]==lungime)recons(lungime,p1-1,p2);
            else recons(lungime,p1,p2-1);
        }
    }
}

int main()
{
    cin.getline(s,3010);
    cin.getline(t,3010);

    n=strlen(s);
    m=strlen(t);

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1])
            {
                d[i][j]=d[i-1][j-1]+1;
            }
            else
            {
                d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
        }
    }

    recons(d[n][m],n,m);

    return 0;
}


Measured memory_bytes: 35584
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
void _main() {
	int N;
	cin >> N;
	double sum = 0;
	rep(i, 0, N) {
		double x;
		string u;
		cin >> x >> u;
		if (u == "BTC") {
			x *= 380000.0;
		}
		sum += x;
	}
	cout << sum << endl;
}

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

int main(){
    int n;
    cin >> n;
    unordered_set<string> s;
    for(int i = 0; i < n; i++){
        string a;
        cin >> a;
        s.insert(a);
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 17612
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int h = scanner.nextInt();
		int w = scanner.nextInt();
		int n = scanner.nextInt();
		int sr = scanner.nextInt()-1;
		int sc = scanner.nextInt()-1;
		char[] S = scanner.next().toCharArray();
		char[] T = scanner.next().toCharArray();

		int r = 0;
		int l = 0;
		int u = 0;
		int d = 0;
		for (int i=0; i<n; i++){
			switch (S[i]){
				case 'R':
					r++;
					if (r>(w-1)-sc) no();
					break;
				case 'L':
					l++;
					if (l>sc) no();
					break;
				case 'U':
					u++;
					if (u>sr) no();
					break;
				case 'D':
					d++;
					if (d>(h-1)-sr) no();
					break;
			}
			switch (T[i]){
				case 'L':
					if (r>-sc)r--;
					break;
				case 'R':
					if (l>sc-(w-1)) l--;
					break;
				case 'D':
					if (u>sr-(h-1)) u--;
					break;
				case 'U':
					if (d>-sr) d--;
					break;
			}
		}
		System.out.println("YES");
	}

	static void no() {
		System.out.println("NO");
		System.exit(0);
	}
}

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

int main()
{
	char str;
	int ans = 0, save = 0,  x = true;
	
	while (scanf("%c", &str) != EOF){
		if (str >= '0' && '9' >= str){
			if (!x){
				save *= 10;
			}
			save += str - '0';
			x = false;
			//printf("[%d]", ans);
		}
		else {
			ans += save;
			save = 0;
			x = true;
		}
	}
	
	printf("%d\n", ans);
}

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

public class Main {

    private static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(final String[] args) throws IOException {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out, true);

        String s = in.next();
        String t = in.next();
        int a = in.nextInt();
        int b = in.nextInt();
        String u = in.next();

        if (s.equals(u)) {
            a--;
        } else if (t.equals(u)) {
            b--;
        }
        out.printf("%d %d%n", a, b);
    }
}


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define int long long 
main(){
	int times=0;
	int n;
	cin>>n;
	string s;
	vector<string>v;
	for(int i=0;i<n;i++){
		cin>>s;
		sort(s.begin(),s.end());
		v.emplace_back(s);
	}
	sort(v.begin(),v.end());
	int t=1;
	for(int i=0;i<n-1;i++){
		if(v[i]==v[i+1])t++;
		else{
			if(t>1)times+=t*(t-1)/2;
			t=1;
		}
	}
	if(t>1)times+=t*(t-1)/2;
	cout<<times<<"\n";
}

Measured memory_bytes: 5748
import java.util.Scanner;

 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		double d  = sc.nextDouble();
		double t  = sc.nextDouble();
		double s  = sc.nextDouble();

		System.out.println(d / s <= t ? "Yes" : "No");
		sc.close();
	}
}




Measured memory_bytes: 37348
#include "bits/stdc++.h"
using namespace std;
 
// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
 
 
/*
--------------------------------------------
 
	type
 
--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
//using pair<T1, T2> = p12;
 
/*
--------------------------------------------
 
	container
 
--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
 
/*
--------------------------------------------
 
	repetition
 
--------------------------------------------
*/
#define MAX(a,b) (a>b)?a:b
#define MIN(a,b) (a>b)?b:a
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPS(i,n) for(int i=0; i<(n); i++)
#define REPinit(a,n) for(int i=a; i<(n); i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)
 
//algorithm
//#define SORT(c) sort((c).begin(),(c).end())
 
/*
--------------------------------------------
 
	constant
 
--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
/*
 
	Optimizer
 
*/
//#pragma GCC optimize("Ofast")


/*
 
	Utility Algorithm
 
*/
template <typename T>
void swapAlgorithm(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

LL euclideanAlgorithm(LL a, LL b) {
    LL a_tmp = a;
    LL b_tmp = b;

    if (a_tmp > b_tmp) {
        swapAlgorithm<LL>(a_tmp, b_tmp);
    }

    LL r = a_tmp % b_tmp;
    while (r != 0) {
        a_tmp = b_tmp;
        b_tmp = r;
        r = a_tmp % b_tmp;
    }
    return b_tmp;    
}

LL getLCM(LL a, LL b) {
    return (a * b)/(euclideanAlgorithm(a, b));
}

/*
  Code
*/

double eauclidDistance(pair<double, double>& x1, pair<double, double>& x2) {
  return sqrt((x1.first - x2.first) * (x1.first - x2.first) + (x1.second - x2.second) * (x1.second - x2.second));
}

void swap(int& a, int& b) {
  int tmp;
  tmp = a;
  a = b;
  b = tmp;
}

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

  vector<int> cost(N+1,0);
  int A;
  REP(M) {
    cin >> A;
    cost[A] = 1;
  }

  int ansRight = 0, ansLeft = 0;
  for (int i = 1; i < X; i++) ansRight += cost[i];
  for (int i = X+1; i <= N; i++) ansLeft += cost[i];
  
  cout << min(ansRight,ansLeft) << endl;

  return 0;
}


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

a = sorted(map(int, input().split()))
tmp  = (a[2] // 2)
# print(a[0] * a[1] * tmp)
# print(a[0] * a[1] * (a[2] - tmp))
print((a[0] * a[1]) * (a[2] - 2 * tmp))


Measured memory_bytes: 3064
#include<stdio.h>
#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

void dig(){
  int minv,d[MAX],iro[MAX];
  int i,j,u,v;
  for(i=0;i<n;i++){
    d[i]=INFTY;
    iro[i]=WHITE;
  }
  d[0]=0;
  iro[0]=GRAY;
  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && iro[i]!=BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1)break;
    iro[u]=BLACK;
    for(v=0;v<n;v++){
      if(iro[v]!=BLACK && M[u][v]!=INFTY){
	if(d[v]>d[u] + M[u][v]){
	  d[v]=d[u]+M[u][v];
	  iro[v]=GRAY;
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d ",i);
    if(d[i]==INFTY)printf("-1\n");
    else printf("%d\n",d[i]);
  }
}

int main(){
  int i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }
  int k,c,u,v;
  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      scanf("%d",&c);
      M[u][v]=c;
    }
  }
  dig();

  return 0;
}

Measured memory_bytes: 636
#include<iostream>

using namespace std;

int main(){
  int a,b;cin>>a>>b;
  if (a > 0){
    cout<<"Positive"<<endl;
  }else if(a == 0 || b == 0){
    cout<<"Zero"<<endl;
  }else if(b < 0){
    if ((b - a) % 2 == 0){
      cout<<"Negative"<<endl;
    }else if((b-a)%2 != 0){
      cout<<"Positive"<<endl;
    }
  }else if(b>0 && a<0){
    cout<<"Zero"<<endl;
  }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n;
  cin >> n;
  if(n%10==3){
    cout << "bon" << endl;
  }
  else if(n%10==0||n%10==1||n%10==6||n%10==8){
    cout << "pon" << endl;
  }
  else{
    cout << "hon" << endl;
  }
}

Measured memory_bytes: 3628
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    AIN(ll, A, N);
    ll ans = 0;
    REP1(i, N - 1)
    {
        if (A[i] < A[i - 1])
        {
            ans += A[i - 1] - A[i];
            A[i] = A[i - 1];
        }
    }
    OUT(ans);
}

Measured memory_bytes: 4844
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ab.append(b)
    if b == n:
        ab.append(a)

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 72920
# -*- using:utf-8 -*-

class main:
  def function(n, a):
    mod = 10 **9 +7
    S = [0] * (n + 1)
    for i in range(n):
      S[i + 1] = S[i] + a[i]
    SN = S[-1]
    ans = 0
    for i in range(n - 1):
      cnt = a[i] * (SN - S[i + 1])
      ans += cnt
    print(ans % mod)



if __name__ == "__main__":
  n = int(input())
  a = list(map(int, input().split()))
  main.function(n,a)


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> maze(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> maze[i][j];

    auto is_black = [&](int x, int y) {
        if (maze[x][y] == '#')
            return true;
        else
            return false;
    };

    bool ok = true;
    repeat(i, 1, h - 1) repeat(j, 1, w - 1) {
        if (is_black(i, j)) {
            if (!is_black(i - 1, j) and !is_black(i, j - 1) and !is_black(i + 1, j) and !is_black(i, j + 1)) ok = false;
        }
    }

    if (ok)
        CYES;
    else
        CNO;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
typedef unsigned long long BITMASK; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<long long, long long> pll;
#define has_bit(bit_mask, x) ((bit_mask) & (1ULL << (x)))
#define turn_on_bit(bit_mask, x) (bit_mask |= (1ULL << (x)))
#define turn_off_bit(bit_mask, x) (bit_mask &= (~(1ULL << (x))))
#define smallest_on_bit(bit_mask) (__builtin_ctzint((bit_mask) & (-(bit_mask))))
#define CLOCK_START clock_t chrono_clk_beg = clock()
#define CLOCK_END clock_t chrono_clk_end = clock(); cerr << (double(chrono_clk_end - chrono_clk_beg) / CLOCKS_PER_SEC) << " sec"
#define bug(args ...) cerr << __LINE__ << ">> ", err(new istringstream(string(#args)), args), cerr << '\n'
#define decToBin(name, num) string name = bitset<8>(num).to_string();
#define binToDec(name, binary) unsigned long name = bitset<8>(binary).to_ulong();
#define radToDeg(name, radians) double name = radians * 180 / M_PI;
#define all(x) x.begin(), x.end()
#define removeDuplicates(vec) sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define printMat(mat) for (auto &x : mat) { for (auto &y : x) { if (y < INF) cout << setw(7) << y; else cout << setw(7) << "-"; } cout << '\n'; }
#define fillMat(mat, n, m, x) for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) mat[i][j] = x;
#define printArr(arr) for (auto &x : arr) cout << x << " "; cout << '\n';
#define arrReplace(arr, from, to) for (auto &x : arr) if (x == from) x = to;
#define INF (1LL<<30)
#define INF32 (1LL<<62)
#define F first
#define S second
#define M_PI 3.14159265358979323846
inline int ceil(int a, int b) { return (a+b-1)/b; }
void err(istringstream *iss) {} template<typename T, typename ... Args> void err(istringstream *iss, const T &_val, const Args & ... args) { string _name; *iss >> _name; if (_name.back()==',') _name.pop_back(); cerr << _name << " = " << _val << "; ", err(iss, args ...); }
int str_replace(string& str, const string& from, const string& to, int limit = -1) { if(from.empty()) return 0; size_t start_pos = 0; int cnt = 0; while((start_pos = str.find(from, start_pos)) != std::string::npos) { str.replace(start_pos, from.length(), to); start_pos += to.length(); cnt++; if (cnt == limit) break; } return cnt; }
#define MOD 1000000007
#define int ll

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int k, n; cin >> k >> n;
	vector<int> arr(n);
	for (auto &x : arr) cin >> x;
	int ans = INF;
	for (int i = 0; i < n; ++i)
	{
		int cur = (i == 0) ? (arr[n-1] - arr[i]) : (k - arr[i] + arr[i-1]);
		ans = min(ans, cur);
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 1792
/* aoj1350  */
//提出用(アクセプトされました)
#include<stdio.h>
#include <stdlib.h>  // qsort
#define N 500  //島の数の最大
#define M 50000 //橋の数の最大

int mst[M]={0};  //最初に作った最小木の橋を記憶する
int flag=0;      //最小木が1度作られたかどうか
int rm = -1;   //取り除いた橋の番号(初期値-1)

//橋を定義
typedef struct bridge{  
    //始点の島,終点の島,コスト
    int s; int d; int c;
}bridge_t;

//比較関数(qsort用)
int cmp(const void *a,const void *b){
  return ((bridge_t*)a)->c - ((bridge_t*)b)->c;
}

//与えられた要素の木の根を再帰で求める関数
int u_root(int x,int number[]){
    //根
    if(number[x-1] == x)
        return x;

    //経路圧縮
    else
        return number[x-1] = u_root(number[x-1],number);
}

//xとyが同じ集合に属するか否かを根を見て判断する(同じなら1を返す)
int u_find(int x, int y, int number[]){
    return u_root(x,number) == u_root(y,number);
}

//xとyの属する集合を併合
void u_union(int x, int y, int number[]){     //x,yは島の番号(1~)を表す
    number[y-1] = x;
}

//全ての要素が同じ集合に含まれているかどうかをfindで判定する関数
int allsame(int n, int number[])
{
    int y;
    for(y=2;y<=n;y++)
            if(!u_find(1,y,number)) //一つでも同じ集合に含まれない要素があるなら0を返す
                return 0;
    return 1; //全ての要素が同じ集合に含まれていれば1を返す。
}


//クラスカル法で最小全域木を生成する関数
//異常終了(最小木が生成できなかった)の時は0を返す
int kruskal(bridge_t b[], int n, int m, int number[]){
    int i=0; //配列の添字
    int mc=0;  //最小木のコスト
    //独立した点がなくなるまで繰り返す
    while(!allsame(n,number)){
        //独立していてかつ取り除かれた橋でないならその要素の根を合成する
        if(!u_find(b[i].s,b[i].d,number) && i!=rm){
            u_union(u_root(b[i].s,number),u_root(b[i].d,number),number);
            //まだ一度も最小木が作られていないならどの橋を使ったかを記憶する
            if(!flag)
                mst[i] = 1;
            //コストを足していく
            mc += b[i].c;
        }
        i++;
        //最後まで探索して、一つでも同じ集合にない要素があれば、最小木は作れないということになる
        if(i==m)
          if(!allsame(n,number))
             return 0;
    }
    return mc;
}

int main(void){
    int n,m;        //島の数,橋の数
    bridge_t b[M];  //橋の情報
    int mc;         //最初に作った最小木のコスト
    int mc2;        //2回目以降に作る最小木のコスト
    bridge_t temp;  //橋の情報の一時記憶領域
    int number[N];  //親の番号
    int alt[M] = {0};     //オルタナティブな橋の番号(初期値は全て非オルタナティブ))
    int acost=0,abridge=0;    //オルタナティブな橋のコストの和と、オルタナティブな橋の本数の和
    int i,j;

    scanf("%d%d",&n,&m);
    //n要素で初期化(初めは全ての頂点が根)
    for(i=0;i<n;i++)
        number[i] = i+1;
    //橋の始点、終点、コストを入力
    for(i=0;i<m;i++){
        scanf("%d%d%d",&b[i].s,&b[i].d,&b[i].c);
    }
    //qsortによるソート(コストの昇順)
    qsort(b,m,sizeof(bridge_t),cmp);

    //クラスカル法を行う関数を呼び出し
    //全ての要素で最小木を作る
    mc = kruskal(b,n,m,number);
    flag=1;     //１度最小木を作成した

    //numberを初期化
    for(i=0;i<n;i++){
        number[i] = i+1;
    }
    //作った最小木の中で辺を一つだけ取り除き最小木が作れるかどうかで場合分け
    for(j=0;j<m;j++){
        //最初に作った最小木の橋ならばその橋を取り除く
        if(mst[j]){
            rm = j;   //取り除いた橋の番号を記憶
            mc2 = kruskal(b,n,m,number);    //橋を一つ取り除いて最小木を作る
            //ある橋を一つ取り除いて同じコストの最小木を作れないなら、それは不変の橋である
            if(mc < mc2 || mc2 == 0)
                alt[j]=1;
            //numberを初期化しておく
            for(i=0;i<n;i++)
                number[i] = i+1;
        }
        //オルタナティブな橋が見つかれば
        if(alt[j]){
            abridge++;
            acost += b[j].c;
        }
    }
    printf("%d %d\n",abridge,acost);
    
    return 0;
}


Measured memory_bytes: 3036