結果

問題 No.4 おもりと天秤
コンテスト
ユーザー iLL
提出日時 2026-03-07 10:29:25
言語 Fortran
(gFortran 15.2.0)
コンパイル:
gfortran _filename_ -O2 -o ./a.out
実行:
./a.out
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 1,352 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 533 ms
コンパイル使用メモリ 40,944 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-07 10:29:26
合計ジャッジ時間 1,097 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

SUBROUTINE SORT(W, N)
    IMPLICIT NONE
    INTEGER, INTENT(INOUT) :: W(N)
    INTEGER, INTENT(IN) :: N
    INTEGER :: I, J, TMP

    DO I = 1, N
        DO J = 1, N - I
            IF (W(J) > W(J+1)) THEN
                TMP = W(J+1)
                W(J+1) = W(J)
                W(J+1) = TMP
            END IF
        END DO
    END DO

    RETURN
END SUBROUTINE SORT

PROGRAM MAIN
    IMPLICIT NONE
    INTEGER :: N, W_SUM, TAR, I, J, CURR, MAX
    INTEGER, ALLOCATABLE, DIMENSION(:) :: W, A, B

    READ *, N
    
    ALLOCATE(W(N))
    READ *, W(:)

    CALL SORT(W, N)

    W_SUM = SUM(W)
    IF (MOD(W_SUM, 2) /= 0) THEN
        PRINT *, 'impossible'
        RETURN
    END IF

    TAR = W_SUM / 2 - W(N)
    IF (TAR == 0) THEN
        PRINT *, 'possible'
        RETURN
    END IF
    ALLOCATE(A(TAR), SOURCE = 0)
    ALLOCATE(B(TAR))
    B(1) = 0
    CURR = 1
    MAX = 1

    ! PRINT *, W(:)
    ! PRINT *, TAR

    
    DO I = 1, N - 1
        DO J = 1, CURR
            IF (A(W(I) + B(J)) == 0) THEN
                MAX = MAX + 1
                A(W(I) + B(J)) = 1
                B(MAX) = W(I) + B(J)
                IF (B(MAX) == TAR) THEN
                    PRINT *, 'possible'
                    RETURN
                END IF
            END IF
        END DO
        CURR = MAX
    END DO

    PRINT *, 'impossible'
END PROGRAM MAIN
0